【UVA1485】Permutation Counting

典中典题。

由于 \(0\le k\le n\le 1000\)，能猜到做法大概是 \(n^2\) 的动态规划，接下来写方程。

以排列长度划分阶段，该长度下 \(E\) 值划分子问题，容易想到定义 \(f[i][j]\) 表示长度为 \(i\) 的排列 \(E\) 值为 \(j\) 的个数。

考虑如何转移 \(f[i][j]\)。

第一种情况，没有新增的 \(E\) 值，方案数为 \(f[i-1][j]\times(j+1)\)；新增了一个，方案数为 \(f[i-1][j-1]\times(n-k)\)。

发现第 \(i\) 个阶段的值只和第 \(i-1\) 个阶段有关，显然可以滚掉一维。但是对于这道题没有必要（因为多组询问，不如查表输出）。

注意初始化 \(f[i][0]=1\)（即 \(\{1,2,\cdots,i\}\)）的排列。

#include <stdio.h>
long long f[1005][1005];
const int N=1000,K=1000;
const int mod=1000000007;
int main()
{
	int i,j,n,k;
    for(i=1;i<=N;++i)
    {
    	f[i][0]=1;
        for(j=1;j<=K;++j)
        {
            f[i][j]=(f[i-1][j]*(j+1)+f[i-1][j-1]*(i-j))%mod;
        }
    }
    while(~scanf("%d %d",&n,&k))
    {
        printf("%lld\n",f[n][k]);
    }
    return 0;
}