典中典题。
由于 \(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;
}
标签:le,const,Counting,int,long,Permutation,UVA1485,1000
From: https://www.cnblogs.com/Syara/p/17092886.html