分析:记dp[n][k]为n个数,逆序数为k的个数,将dp[n][k]分为两部分,一部分有1~n-1的逆序构成,一类是有n的逆序,可以得到dp[n+1][k+1]=(max(0,k+1-n),min(k+1,n*(n-1)/2)∑dp[n][i],再用dp[n+1][k+1]与dp[n+1][k]做差,讨论一下k和n的关系就可以写出递推式了.
1 #include<iostream> 2 using namespace std; 3 const int maxn=1005,maxk=20005,p=1e9+7; 4 int dp[maxn][maxk]; 5 int main(){ 6 dp[1][0]=1; 7 for(int n=1;n<maxn-1;n++){ 8 dp[n+1][0]=1; 9 for(int k=0;k<n*(n+1)/2&&k<maxk-1;k++){ 10 dp[n+1][k+1]=dp[n+1][k]; 11 if(k>=n) 12 dp[n+1][k+1]-=dp[n][k-n]; 13 if(k+1<=n*(n-1)/2) 14 dp[n+1][k+1]+=dp[n][k+1]; 15 dp[n+1][k+1]%=p; 16 if(dp[n+1][k+1]<0)dp[n+1][k+1]+=p; 17 } 18 } 19 int t,n,k; 20 cin>>t; 21 while(t--){ 22 cin>>n>>k; 23 cout<<dp[n][k]<<endl; 24 } 25 return 0; 26 }
原文：http://www.cnblogs.com/7391-KID/p/7043981.html