Problem
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。
1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。
1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3
由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。
Solution
递推公式为f(n,k)=f(n,k−1)+f(n−1,k)−f(n−1,k−n)。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include<stdio.h> #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; int T,nn,kk; struct E{ int n,k; }e[10020]; int mxn; int f[1010][20020]; const int mod=1e9+7; int mx[1010]; inline int mo(int x){ return x>=mod?x%mod:x>=0?x:mo(x+mod); } int main(){ scanf("%d",&T); for(int i=1;i<=T;i++){ scanf("%d%d",&e[i].n,&e[i].k); mxn=max(mxn,e[i].n); mx[e[i].n]=max(mx[e[i].n],e[i].k); } for(int i=0;i<=mxn;i++){ f[i][0]=1; } for(int i=mxn;i>=1;i--){ if(mx[i]>mx[i-1]) mx[i-1]=mx[i]; } for(int i=1;i<=mxn;i++){ for(int j=1;j<=mx[i];j++){ int t=j-i>=0?f[i-1][j-i]:0; f[i][j]=mo(f[i][j-1]+f[i-1][j]-t); } } for(int i=1;i<=T;i++){ printf("%d\n",f[e[i].n][e[i].k]); } return 0; }
|