hdu5225 Tom and permutation(BestCoder Round #40)

hdu5225 Tom and permutation(BestCoder Round #40)

Tom and permutation

问题描述

Tom学会了通过写程序求出一个1-n的排列的逆序对数，但他的老师给了他一个难题：给出一个1-n的排列，求所有字典序比它小的1-n的排列的逆序对数之和。Tom一时不知道该怎么做，所以他来找你帮他解决这个问题。因为数可能很大，答案对109+7取模。

输入描述

输入包含多组数据（大约20组）。对于每一组数据，第一行一个正整数n，第二行n个数，是一个n的排列。n≤100

输出描述

对于每组数据输出一行，答案模109+7。

输入样例

3 2 1 3 5 2 1 4 3 5

输出样例

1 75

Hint

由于输入文件可能较大，建议对读入进行优化

当时看不懂题意，后来问了问群里的朋友。

Problem B从1到n枚举k，表示当前要计算的排列与读入的排列前k-1项相同，而第k项不同。对于每一个k，再枚举一个t，表示当前要计算的排列的第k项是t，所以t要比读入的排列的第k项小，并且不与前k-1个数中的任意一个数相等。那么，剩下的n-k个数任意排列，都满足字典序小于读入的排列。所以要计算它们的逆序对数之和。可以分情况计算：1、逆序对中的两个数都在前k-1个位置，可以对于每一个k都暴力计算。2、逆序对中的一个数在前k-1个位置，另一个数不在，同样可以对于每一个k都暴力计算。3、逆序对中的一个数在第k个位置，另一个数在后n-k个位置。也可以暴力计算。4、逆序对中的两个数都在后n-k个位置。这个值可以DP预处理，也可以推出一个式子直接计算。可以这样考虑：在后n-k个位置中，有一半的排列方式中，第i小的数在第j小的数(i>j)的前面。共有(n-k)!种排列方式，所以对于一对数，有(n−k)!2种排列方式中是逆序对。共(n−k)⋅(n−k−1)2对数，所以这类逆序对共(n−k)⋅(n−k−1)⋅(n−k)!4对。时间复杂度：O（n3）

题意是：

首先列举出所有比给定序列字典序小的序列， 然后对于每个列举出来的序列，求逆序数和， 然后对所有逆序数和再求和， 就是所求答案

#include#include#include#include#include#include#define maxn 110#define mod 1000000007using namespace std;typedef long long LL;typedef unsigned long long ULL;int n,a[maxn],F[maxn],fact[maxn];void Prepare(int n){ fact[0]=1; for(int i=1;i<=n;i++) fact[i]=(LL)fact[i-1]*i%mod,F[i]=(LL)i*(i-1)/2*fact[i]%mod*(1+mod)/2%mod;}void read(){ for(int i=1;i<=n;i++) scanf("%d",a+i);}int work(){ static bool use[maxn]; static int sum[maxn]; int ans=0; memset(sum,0,sizeof(sum)); memset(use,false,sizeof(use)); int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;jj; val+=cnt; for(int k=1;k<=n;++k) if(k!=j&&!use[k]){ val+=sum[k]; val+=ka[i]; for(int j=a[i];j>=1;--j) ++sum[j]; use[a[i]]=true; } return ans;}int main(){ Prepare(100); while(cin>>n){ read(); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。