传送门

分析

可以发现，这 $n$ 个人本质是相同的，因此可以设 $dp_{i,j}$ 为：已有 $i$ 个人拉手，恰好围成 $j$ 个圈的方案数。
第 $i$ 个人就一定会被插进一个圆或组成一个圆。

• 当他插入进一个圆时，由于每种方法的圆本质相同，并且每个方法的每个圆中的可以插入的空位的和为总人数乘上方案数，即为 $(i-1) \times dp_{i-1,j}$

• 当他组成一个圆时，必须要以前的两个人和他一起组成，由于每个人的本质相同，因此有 $(i-1) \times (i-2)$ 种选人的方案，而且当人数为 $i-3$ 时，方案数为 $dp_{i-3,j}$ ，因此总方案数为 $(i-1) \times (i-2) \times dp_{i-3,j}$。

Code

#include <bits/stdc++.h>
using namespace std;
long long n,k,p,f[3001][3001];
int main(){
	cin>>n>>k>>p;
	f[0][0]=1;
	f[1][0]=f[2][0]=0;
	for(int i=3;i<=n;i++){
		for(int j=k;j>=1;j--){
			f[i][j]=((f[i-1][j]*(i-1)%p)+((f[i-3][j-1]*(i-1)%p*(i-2)%p)%p))%p;
		}
	} 
	cout<<f[n][k];
}