题目描述: 求由 1 到 n 一共 n 个数字组成的所有排列中，逆序对个数为 k 的有多少个。 输入格式： 第一行为一个整数 T ，为数据组数。 以下 T 行，每行两个整数 n，k，意义如题目所述。 输出格式： 对每组数据输出答案对 10000 取模后的结果。 样例输入： 1 4 1 样例输出： 3 数据规模： 对于 30% 的数据，满足：n≤12； 对于所有数据，满足：n≤1000, k≤1000，T≤10。 题目分析: 假如你已经求出1~n的逆序对个数为k的排列个数，在加入n+1这个数时，那么加在最后一个，k不变;加在最后一个前面，k+1;以此类推；加在第一个前，则k+n。可以感知的是一个动态规划，再手算出前几个，寻找规律。得到转移方程： f[i][j]=f[i-1][j]+f[i][j-1],(i>j); f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-i],(i≤j); 附代码:
#include<iostream> #include<cstring> #include<string> #include<cstdlib> #include<cstdio> #include<ctime> #include<queue> #include<cmath> #include<iomanip> #include<cctype> #include<set> #include<map> #include<algorithm> using namespace std; int t,n,f[1010][1010]; struct node{ int n; int k; }a[100]; int main() { //freopen("permut.in","r",stdin); //freopen("permut.out","w",stdout); scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%d%d",&a[i].n,&a[i].k); n=max(n,a[i].n); } f[2][0]=1; f[2][1]=1; f[3][0]=1; f[3][1]=2; f[3][2]=2; f[3][3]=1; for(int i=4;i<=n;i++) for(int j=0;j<=1000;j++) if(j==0) f[i][j]=1; else { if(i>j) f[i][j]=(f[i-1][j]+f[i][j-1])%10000; else f[i][j]=(f[i-1][j]+f[i][j-1]-f[i-1][j-i]+10000)%10000;//应为在模后，前两个可能小于第三个，就会成为负的 } // 需要加10000，保持正确性，很容易没考虑到，需注意 for(int i=1;i<=t;i++) printf("%d\n",f[a[i].n][a[i].k]); return 0; }