神秘二项式反演 + EGF 推导题目。
题意：有 $n$ 个 $[1, D]$ 的随机变量，求至少能组成 $m$ 个相同数字的二元组的方案数。$n, m\leq 10 ^ 9$，$ D\leq 10 ^ 5$。
显然可以计算出现次数为奇数的 $\leq n - 2\times m$ 个。
首先特判 $2\times m>n$ 和 $2\times m\leq n - D$ 的情况，答案分别为 0 和 $D ^ n$。
容易发现我们需要对整个序列使用 EGF。我们知道 $\{a, a ^ 2, a ^ 3, \cdots\}$ 的 EGF 是 $e ^ {ax}$，那么 $\{1,1, 1, \cdots\}$ 的 EGF 是 $e ^ x$，$\{1, -1, 1, -1\}$ 的 EGF 是 $e ^ {-x}$，那么我们只要奇数的，那么就是 $\dfrac{e ^ x - e ^ {-x}}{2}$。
那么我们现在需要计算 $\forall k\in [1, n - 2\times m]$ 的答案，记为 $f(k)$。
这个是一个恰好的形式，然后考虑二项式反演，计算钦定 $k$ 个为奇数的答案，记为 $g(k)$。
按照刚才的 EGF，我们可以写出 $g(k)$ 的生成函数：
最后一步是二项式定理展开。然后我们就可以得到 $g(k)$ 的表达式：
于是可以卷积计算 $g(k)$，时间复杂度 $O(D\log D)$。
然后按照 Luogu P4491 染色 的套路，容易把二项式反演的过程卷积加速，于是总复杂度 $O(D\log D)$。
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
| int main() {
init();
int D, n, m;
std::cin >> D >> n >> m;
if (2 * m > n)
return puts("0"), 0;
if (2 * m <= n - D)
return printf("%d\n", qpow(D, n)), 0;
poly a(D + 1), b(infact, infact + D + 1);
for (int i = 0, op = 1, tmp; i <= D; ++ i, op = Mod - op)
a[i] = qpow(adj(tmp = D - 2 * i), n) * (LL) infact[i] % Mod * op % Mod;
a = a * b, a.resize(D + 1);
for (int i = 0; i <= D; ++ i)
a[i] = (LL) a[i] * fact[D] % Mod * infact[D - i] % Mod * qpow(2, Mod - 1 - i) % Mod;
for (int i = 0; i <= D; ++ i)
a[i] = (LL) a[i] * fact[i] % Mod;
for (int i = 0; i <= D; ++ i)
if (i & 1)
adj(b[i] = -b[i]);
std::reverse(b.begin(), b.end());
a = a * b;
for (int i = 0; i <= D; ++ i)
a[i + D] = (LL) a[i + D] * infact[i] % Mod;
int res = 0;
for (int i = 0; i <= n - 2 * m; ++ i)
adj(res += a[i + D] - Mod);
std::cout << res << std::endl;
return 0;
}
|