题目链接
这是一道鸽子题.
解题思路
每次鸽子回到鸽笼时会影响概率大小, 即令 $a_i$ 减 $1$ 时会影响鸽笼总数. 但根据「PKUWC2018」猎人杀 的结论, 认为每次选择鸽笼时, 若有 $a_i > 0$, 则直接令 $a_i$ 减 $1$; 否则再次选择.
也就是说, 可以认为已经满的鸽笼列仍可入住鸽子, 但对 $a_i$ 没有影响. 此时计算出的结果和原来限制下的结果相同.
此时将鸽子的入住顺序用一长度为 $m$ 的有标号序列描述, 序列中第 $i$ 个元素表示第 $i$ 次选择, 某只鸽子入住鸽笼的列编号. 容易发现 $m \ge N$, 因为可以重复入住, 但每只鸽子都要回到鸽笼.
不妨假设当前空出的鸽笼在第 $1$ 列, 那么序列中一定存在 恰好 $a_1 - 1$ 个 $1$, 同时对于其余每个元素 $i$, 至少 出现 $a_i$ 次. 类似于【集训队作业2018】喂鸽子 的思路, 可得出该序列个数的 EGF $F(x)$ 为
那么计算出所有合法序列的数量, 并将最后结果除以序列个数的总数就能够得出空出鸽笼在第 $1$ 列的答案. 同时, 对每个元素做一次类似的操作即可计算最终结果.
但是 $e ^ x$ 展开后有无穷项系数, 不便于计算. 此时有一个思路 (from yhx-12243), 将 $F(x)$ 视为 $x$ 和 $e ^ x$ 的二元生成函数, 那么有
对于其中一项 $y ^ i x ^ j = e ^ {ix} x ^ j$, 其对答案的另有除其系数以外的贡献. 取 $e ^ x$ 第 $s$ 项, 则
此时 $F(x, y)$ 各项只同 $x$ 有关. 假定 $s + j = m$, 那么 $F(x, y)$ 第 $m$ 项对答案的贡献为
其中 $n ^ {m + 1}$ 长度为 $m$ 的序列总个数. 考虑到 $a_1$ 个鸽笼中必须剩下一个不选, 且该限制不好直接计算. 那么在计算序列总数时直接将 $a_1$ 添加到序列中, 那么每次选择都有 $n$ 种可能, 因此总数为 $n ^ {m + 1}$.
实际计算时, 我们需要求得每一项的结果的和. 即
根据广义二项式定理, 原式可化为
只需枚举 $i$, $j$ 即可, 实际计算时还需乘上对应项系数, 同时要考虑 $\frac{x ^ {a_1 - 1} }{(a_1 - 1)!}$ 的影响.
对于每一种空出鸽笼的位置, 重新计算 $F(x)$ 的时间复杂度过高. 因此可直接计算
每次在原有基础上除 $e ^ x - \sum\limits_{k = 0} ^ {a_i - 1} \dfrac{x ^ k}{k!}$ 即可. 具体实现时将乘法 “倒过来写” 就好了.
时间复杂度为 $O\big(n ^ 2 \left( \sum a_i\right) \cdot \max \{ a_i \}\big)$.
代码实现
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN = 3e1 + 5, MAXM = MAXN * MAXN, P = 998244353;
int fac[MAXM], ifac[MAXM], inv[MAXM];
int fpow(int base, int b) {
int ret = 1;
while (b > 0) {
if (b & 1) ret = 1LL * ret * base % P;
base = 1LL * base * base % P, b >>= 1;
}
return ret;
}
void PolyPre(int N) {
inv[1] = 1;
for (int i = 2; i <= N; ++i)
inv[i] = 1LL * inv[P % i] * (P - P / i) % P;
ifac[0] = fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = 1LL * fac[i - 1] * i % P;
ifac[i] = 1LL * ifac[i - 1] * inv[i] % P;
}
}
inline int pls(int& a, const LL& b) { return a = (a + b) % P; }
inline int mns(int& a, const LL& b) { return a = (a - b + P) % P; }
int n;
int A[MAXN], h[2][MAXN][MAXM], g[MAXN][MAXM];
int main() {
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", A + i);
PolyPre(MAXM - 1);
int cur = 1, df = 0;
h[cur][0][0] = 1;
for (int i = 0; i < n; ++i) {
memset(h[cur ^ 1], 0, sizeof h[cur ^ 1]);
for (int j = 0; j <= i; ++j)
for (int k = 0; k <= df; ++k) if (h[cur][j][k] > 0) {
pls(h[cur ^ 1][j + 1][k], h[cur][j][k]);
for (int l = 0; l <= A[i + 1] - 1; ++l)
mns(h[cur ^ 1][j][k + l], 1LL * ifac[l] * h[cur][j][k] % P);
}
cur ^= 1, df += A[i + 1] - 1;
}
int (*f)[MAXM] = h[cur];
for (int m = 1; m <= n; ++m) {
memset(g, 0, sizeof g);
for (int j = n - 1; j >= 0; --j)
for (int k = 0; k <= df - A[m] + 1; ++k) {
pls(g[j][k], f[j + 1][k]);
if (j == 0 || g[j][k] == 0) continue;
for (int l = 0; l <= A[m] - 1; ++l)
pls(g[j - 1][k + l], 1LL * ifac[l] * g[j][k] % P);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int j = A[m] - 1;
for (int k = 0; k <= df - A[m] + 1; ++k, ++j) if (g[i][k] > 0)
pls(ans, 1LL * fac[j] * g[i][k] % P * fpow(inv[n - i], j + 1) % P);
}
ans = 1LL * ans * ifac[A[m] - 1] % P;
printf("%d%c", ans, " \n"[m == n]);
}
return 0;
}
|
参考资料
我承认我不可能写地比参考资料好 (
