NC20205. [JSOI2013]游戏中的学问
描述
输入描述
输入一行包含三个正整数N，k和P.
3 ≤ 3k ≤ N ≤ 3000，10^4 ≤ p ≤ 2×10^9
输出描述
输出文件的包含一行一个整数，表示本质不同的方案数对p的余数。
保证p一定是一个质数。
示例1
输入:
3 1 1000000009
输出:
2
C++ 解法, 执行用时: 42ms, 内存消耗: 12152K, 提交时间: 2021-08-09 08:26:37
#include<cstdio>
using namespace std;
int dp[3005][1005];
int main(){
int n,k,p;
scanf("%d%d%d",&n,&k,&p);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j]=(dp[i-1][j]*(i-1))%p;
if(i>=3) dp[i][j]=(dp[i][j]+dp[i-3][j-1]*(i-1)%p*(i-2)%p)%p;
}
}
printf("%d",dp[n][k]);
return 0;
}