题解 P5259 【[JSOI2013]游戏中的学问 】

mqxmm · 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;
}