HDU 3664 Permutation Counting(DP)

題目鏈接

弱爆啦，組合弱爆了，反正是沒想出來怎么搞這個題，其實這個公式不難推啊，反正就是沒推出來。今天隊內賽，實在是沒辦法了，暴力寫了個DFS，先把10以內的打出表來，發現類似楊輝三角的一個表，推不出公式，只能找規律了。也推公式，也找規律，中間還走會了神，發現borad上過的人N多了，有些著急，這樣應該不難吧。。。又推了會，還是沒想出來，找規律吧，估摸著應該是和上兩項有關系，自己寫了小程序測試一下幾個數據和scf討論了下，貌似真的是找出規律了。。。然后時間不多了，好在代碼很短，馬上快結束了，亂寫了，最后在各種亂搞+思考之下，和暴力的寫的數據對上了，中間錯了2次，好在在4:53的時候終于AC了。。。。

公式的意義：p[i][j] = (i-j)*p[i-1][j-1] + (j+1)*p[i-1][j];對最后一個數進行討論，最后一個數字，如果和a[i] > i的位置交換，最后一個數一定比那個位置大，所以之前就必須有j個a[i] > i的數，所以方案數為(j+1)*p[i-1][j] +1代表最后一個數的位置，如果最后一個數和a[i] < i的位置交換共有(i-1) - (j-1)個 ，則方案數為(i-j)*p[i-1][j-1]。

#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 1000000007
__int64 p[1001][1001];
int main()
{
    int i,j,n,k;
    for(i = 1;i <= 1000;i ++)
    {
        p[i][0] = 1;
        p[i][i-1] = 1;
    }
    for(i = 3;i <= 1000;i ++)
    {
        for(j = 1;j <= (i+1)/2-1;j ++)
        {
             p[i][i-1-j] = p[i][j] = (((i-j)*p[i-1][j-1])%MOD+((j+1)*p[i-1][j])%MOD)%MOD;
        }
    }
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        printf("%I64d\n",p[n][k]);
    }
    return 0;
}