神犇学长(zay)出的题，代码很简短的一道动态规划，拿出来做一做
(Describe)
大家应该都见过很多人手拉手围着篝火跳舞的场景吧？一般情况下，大家手拉手跳舞总是会围成一个大圈，每个人的左手拉着旁边朋友的右手，右手拉着另 一侧朋友的左手。
不过，如果每一个人都随机的拉住两个不同人的手，然后再慢慢散开，事情 就变得有趣多了——此时大家依旧会形成圈，不过却可能会形成多个独立的圈。 当然这里我们依然要求一个人的右手只能拉另一个人的左手，反之亦然。
班里一共有 (N) 个同学，由 (1) 到 (N) 编号。(Will)想知道，究竟有多少种本质不 同的拉手方案，使得最终大家散开后恰好形成 (k) 个圈呢？
给定两种方案，若存在一个人和他的一只手，满足在这两种方案中，拉着这 只手的人的编号不同，则这两种方案本质不同。
输入输出格式
输入格式：
输入一行包含三个正整数(N,k,P)
输出格式：
输出文件的包含一行一个整数，表示本质不同的方案数对(p)的余数。保证(p) 一定是一个质数。
(Solution)
标准 (DP)题，统一把左手看成单向边，就转换成多环计数了（环大小 (>=3)），有点错排问题的味道。
直接用$ f_{i,j}$ 表示已选 (i) 个点，构成 (j) 个环的方案数。
怎么构成一个新环呢？要先有个小目标——构造三个点的。转移来的状态是 (f_{i-3,j-1}) ,新加进去了 (i-1) 和 (i-2) 号点，钦定 (i) 号点是这个环中的“头儿”，也就是说 (i-1) 和 (i-2) 号点可以跟之前使用的点交换，所以转移贡献是 (f_{i-3,\,j-1} imes(i-1) imes(i-2))
但大小为 (3) 远远不够，我们也可以钦点 (i) 号点是用来扩充的。转移来的状态是 (f_{i-1,j})，因为其可以接在前 (i-1) 个点的任何一个点的后面，所以转移贡献是 (f_{i-1,j} imes(i-1))。
综上，转移方程是(f_{i,j} = f_{i-3,j-1} imes(i-1) imes(i-2)+f_{i-1,j} imes(i-1))，注意设定边界 (f_{0,0} = 1)
答案为(f_{n,k})，注意取模。
(Code)
#include<cstdio>
#include<iostream>
#define maxn 1005
using namespace std;
int n,k,p;
long long dp[maxn<<2][maxn];
int main()
{
scanf("%d%d%d",&n,&k,&p);
dp[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=min(i/3,k);++j)
dp[i][j]=(dp[i-1][j]*(i-1)%p+dp[i-3][j-1]*(i-1)*(i-2)%p)%p;
printf("%lld",dp[n][k]);
}