模板一点的生成函数题目。
题意：给定 $n$ 个点到 1 的距离，问有多少边数为 $m$ 的无向图满足该限制。边权均为 1，设 $cnt_i$ 表示距离为 $i$ 的点数，则 $n\leq 10 ^ 5$，$m\leq 2\times 10 ^ 5$，$\sum_i cnt_icnt_{i - 1}\leq 2\times 10 ^ 5$，3s，保证至少有一组解。
首先，我们容易发现，按照 $dis$ 分层后，只可能在相邻层和同层直接连边，不可能跨层连边。现在分别求他们的生成函数。
首先考虑邻层的生成函数。对于一个点来说，他可以任意向前一层的点连边，但是不能不连边（不然没法保证距离），于是单个点的生成函数为 $(1 + x) ^ {cnt_{i - 1}} - 1$，然后有 $cnt_i$ 个，于是为 $((1 + x) ^ {cnt_{i - 1}} - 1) ^ {cnt_i}$。由于题目保证了 $\sum_i cnt_icnt_{i - 1}\leq 2\times 10 ^ 5$，所以该算法可以直接分治 NTT 计算，时间复杂度 $O(m\log ^ 2 m)$。
然后考虑同层的生成函数。对于一层来说，我们有 $\binom{cnt_i}2$ 条边可供选择，假设总可选数记为 $T = \sum_i\binom{cnt_i}2$，于是可以得到生成函数为 $\sum_{i = 1} ^ T x ^ i \binom Ti$，由于最后答案取的 $m$，只需要到 $m$ 即可。然后有可能 $T$ 比较大，于是使用 Lucas 定理，写出拆分组合数的式子就可以简单的把 $T$ 直接模 998244353。
最后把两个卷积一下，总时间复杂度 $O(m\log ^ 2 m)$，可以通过。
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
| int main()
{
init();
int n, m;
std::cin >> n >> m;
poly cnt(n);
std::vector<poly> all;
for (int i = 1, x; i <= n; ++ i) scanf("%d", &x), cnt[x] ++;
for (int i = 1; i < n; ++ i)
{
if (!cnt[i]) break;
poly cur(cnt[i - 1] + 1);
for (int j = 1; j <= cnt[i - 1]; ++ j) cur[j] = C(cnt[i - 1], j);
for (int cs = 1; cs <= cnt[i]; ++ cs) all.push_back(cur);
}
auto solve = [&](auto &self, poly *a, int l, int r) -> poly {
if (l == r) return a[l];
int mid = (l + r) >> 1;
return self(self, a, l, mid) * self(self, a, mid + 1, r);
};
auto res = solve(solve, all.data(), 0, (int) all.size() - 1);
int tot = 0;
for (int i = 0; i < n; ++ i) adj(tot += C(cnt[i], 2) - Mod);
poly g(m);
for (int i = 0, dn = 1; i < m && i <= tot; ++ i, dn = (LL) dn * (tot - i + 1) % Mod)
g[i] = (LL) dn * infact[i] % Mod;
res = res * g;
std::cout << res[m] << '\n';
return 0;
}
|