hdu 3664 1~n排列（ai>i ) 为k个数

http://acm.hdu.edu.cn/showproblem.php?pid=3664

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

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

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include<set>
#include <iostream>
#include <algorithm>
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<i;j++)
            dp[i][j]=((j+1)*dp[i-1][j]+(i-j)*dp[i-1][j-1])%mod;
    }
    while(~scanf("%d%d",&n,&k))
        printf("%lld
",dp[n][k]);
    return 0;
}
//当i放在dp[i-1][j]的j个位置或就放在第i个位置时。比下标大的数(E数)不会增加
//当第i个数放到dp[i-1][j-1]的(i-1)-(j-1)个位置上时。E数会在dp[i-1][j-1]的基础上增加一个

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].