题面

题解

这个数据范围, 直接 DP 一下就完了
看是这个人新开一个圈还是加到别的圈里去
注意, 新开一个圈最少需要三个人
设 \(f[i][j]\) 为前 \(i\) 个人组成 \(j\) 个圈的方案数
\[ f[i][j] = \begin{cases} f[i - 1][j] * (i - 1)\f[i - 3][j - 1] * (i - 1) * (i - 2)\\end{cases} \]
没了

Code

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;int n, k, mod, f[3005][3005]; template < typename T >inline T read(){ T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * w; }int main(){ n = read <int> (), k = read <int> (), mod = read <int> (); if(n < 3) { puts("0"); return 0; } f[0][0] = 1; for(int i = 3; i <= n; i++) for(int j = 1; j <= min(i / 3, k); j++) f[i][j] = (1ll * (i - 1) * (i - 2) % mod * f[i - 3][j - 1] % mod + 1ll * f[i - 1][j] * (i - 1) % mod) % mod; printf("%d\n", f[n][k]); return 0; }