#48956. 「计蒜客模拟赛」魔法阵
Summarize
$n$ 个有编号的球放到有编号的环上，球分黑白两色，共 $k$ 个白球。要求至少有 $d$ 对黑球相邻，求方案数。
$n\le 1000000$
Solution
可以将编号为 $1..k$ 的小球视为相同的白球，将编号为 $k+1..n$ 的小球视为相同的黑球，在统计答案时乘上 $k!(n-k)!$ 即可。
可以将环视为无编号的环，在统计答案时乘上 $n$ 即可。
注意到“断开的边”只会在一段相邻的白球之间产生，将一段相邻的白球称为一个连通块。设有 $p$ 个连通块，则“断开的边”的数量为 $n-k-p$。根据题目条件 $n-k-p\ge d$，得 $p\le n-k-d$。因此从 $1$ 到 $n-k-d$ 枚举连通块数量。
对于枚举到的 $p$，用隔板法将黑球和白球分成 $p$ 段，并将它们摆放在无编号的环上。可以发现，每种方案会被重复统计 $p$ 次，故两次隔板法求得的方案数需要再除以 $p$。
最后将统计得到的答案乘上 $n\times k!(n-k)!$ 即可。
Note
需要特殊讨论 $k=1$ 和 $k=n$ 的情形，因为黑/白球个数为零，无法划分为连通块。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const ll MOD = 998244353;
ll fac[MAXN], inv[MAXN], facinv[MAXN];
inline ll C(int n, int k) {
return fac[n] * facinv[k] % MOD * facinv[n - k] % MOD;
}
int t, n, k, d;
int main() {
freopen("ring.in", "r", stdin);
freopen("ring.out", "w", stdout);
fac[0] = facinv[0] = fac[1] = inv[1] = facinv[1] = 1;
for (int i = 2; i <= 1000000; ++i) {
fac[i] = 1ll * i * fac[i - 1] % MOD;
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
facinv[i] = inv[i] * facinv[i - 1] % MOD;
}
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &k, &d);
if (k == 0) {
printf("%lld\n", fac[n]);
continue;
} else if (k == n) {
if (d == 0) printf("%lld\n", fac[n]);
else printf("0\n");
continue;
}
ll ans = 0;
for (int p = 1; p <= n - k - d; ++p) {
if (p > k || p > n - k) break;
ans = (ans + C(n - k - 1, p - 1) * C(k - 1, p - 1) % MOD * inv[p] % MOD) % MOD;
}
ans = 1ll * n * ans % MOD;
ans = ans * fac[k] % MOD * fac[n - k] % MOD;
printf("%lld\n", ans);
}
return 0;
}
|