自动搬运

查看原文

来自洛谷，原作者为

	mqxmm 沐晴つ

搬运于2025-08-24 22:08:48，当前版本为作者最后更新于2021-01-05 21:40:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小兔的话

欢迎大家在评论区留言哦~

思路

因为 每一个人都随机地拉住两个不同人的手，我们可以知道 至少要 $3$ 个人才能围成一个新的圈
不妨设 $dp[i][j]$：有 $i$ 个人，围成 $j$ 个圈的方案数

分析

对于一个 $i, j$，有 $2$ 种情况：

• 第 $i$ 个人加入之前的人围成的 $j$ 个的圈中，第 $i$ 个人可以插入之前的 $i - 1$ 个位置（ 大家可以自己推一下, $n$ 个人就有 $n$ 个空位 ），故有 $i - 1$ 种情况，即 $dp[i - 1][j] * (i - 1)$
• 第 $i$ 个人分离出来，和之前的 $2$ 个人围成 $1$ 个新的圈 ( 如果是和之前的 $3$ 个人，就相当于是加入那 $3$ 个人之前围成的圈中了 ），这时只需要选出之前的人中的 $2$ 个人，故有 $(i - 1) * (i - 2)$ 种情况，即 $dp[i - 3][j - 1] * (i - 1) * (i - 2)$

综上所述：$dp[i][j] = dp[i - 1][j] * (i - 1) + dp[i - 3][j - 1] * (i - 1) * (i - 2)$

代码

#include <cstdio>

// 以下定义只是为了好看
#define i32 int
#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long

const int MAXN = 3e3, MAXK = MAXN / 3;
int N, K, P;
i64 dp[MAXN + 5][MAXK + 5];

int main()
{
	scanf("%d %d %d", &N, &K, &P);
	dp[0][0] = 1 % P;
	for (int i = 1; i <= N; i++)
	{
		for (int j = K; j >= 1; j--)
		{
			dp[i][j] = dp[i - 1][j] * (i - 1) % P;
			if (i >= 3) dp[i][j] += dp[i - 3][j - 1] * (i - 1) % P * (i - 2) % P;
			dp[i][j] %= P;
		}
	}
	printf("%lld\n", dp[N][K]);
	return 0;
}