求1~n的排列个数，使得逆序数（ai>i ) 为给定的k.

dp[i][j]表示前1~i的排列中，有j个数是逆序数的个数.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            #include 
            
             #include 
             
              using namespace std;#define RD(x) scanf("%d",&x)#define RD2(x,y) scanf("%d%d",&x,&y)#define clr0(x) memset(x,0,sizeof(x))typedef long long ll;const int INF=0x3f3f3f3f;const int maxn=100010;const int mod=1000000007;ll dp[1010][1010];int main(){ int i,j,n,k; for(i=1;i<=1000;i++) { dp[i][0]=1; dp[i][i]=0; for(j=1;j
             
            
           
          
         
        
       
      
     
    

dp[i][j]=(j+1)*dp[i-1][j]+(i-j)*dp[i-1][j-1].

考虑数i的放的位置，显然要想得到j个逆序数，i是大于前面的，所以只用考虑前面逆序数小于等于j的情况，而且放上这位最多只能增加一个逆序数。如果前面有j个逆序数，将这j个数与i交换，逆序数个数不变，第i个还可以放到第i个位置，此时为（j+1)*dp[i-1][j].当前面逆序数为j-1时，此时要构造一个逆序数，可以把前面的非逆序数与i交换，这样就多增加了一个逆序数，此时为（i-1-(j-1))*dp[i-1][j-1].