2024 ICPC Nanjing C and 2024 ICPC Senyang
ICPC Nanjing C
该算是结论？对于一颗 \(n\) 个节点的外向树（即所有边都是指向叶子方向的），它的拓扑序的数量为 \(n! \over \Pi_u sz_u\)，其中 \(u\) 是树中的节点，\(sz_u\) 是子树 \(u\) 的大小。在一颗树中，我们记 \(cnt_p\) 为以 \(p\) 为根的子树的拓扑序数量，若 \(p\) 的直接儿子是 \(u\)，则我们有 \(p\) 子树中，除去子树 \(u\) 剩余部分的拓扑序数量为 \(x = {cnt_p \over (^{sz_p - 1}_{sz[u]}) cnt_u}\)， \(x\) 可以这样理解：若我知道了 \(x\) 和 \(cnt_u\)，我想去求 \(cnt_p\)，则就要在 \(sz_p - 1\) 个位置中（除掉 \(p\) 必须放在第一个位置）选 \(sz_u\) 个位置给子树 \(u\)，选完位置后乘上子树 \(u\) 的拓扑序数量。
有了以上关于拓扑序的一些公式，我们考虑这道题。可以发现若只考虑点 \(u\) 在拓扑序中的位置，则我们不需要考虑 \(u\) 子树内部。于是我们先删掉 \(u\) 下面的所有点只考虑 \(u\) （也就是树上只有 \(n - sz_u + 1\) 个节点了），记 \(u\) 在拓扑序的第 \(x\) 个位置时且不考虑 \(u\) 的子树的拓扑序的方案数为 \(f_{u, x}\)，则考虑进 \(u\) 的子树后的方案数就是 \((^{n - x}_{sz[u] - 1}) \times cnt_u \times f_{u, x}\)，也就是说只要得到了 \(f_{u, u}\)，我们就知道了 \(u\) 的答案。
接下来我们考虑如何计算 \(f_{u, x}\)。假设 \(u\) 的父节点为 \(p\)，我们就可以尝试由 \(f_{p, y}\) 来计算 \(f_{u, x}\)（显然 \(y < x\)）。\(f_{u, x}\) 相比于 \(f_{p, y}\) 多考虑了 \(u\) 的存在和子树 \(p\) 中除了 \(u\) 子树的其它节点，多考虑的节点的数量为\((sz_p - 1) - (sz[u] - 1)\)，但是对于分配他们的位置，我们只用考虑 \((sz_p - 1) - sz[u]\) 个节点，因为 \(u\) 的位置已经明确知道是 \(x\) 的。选位置的方案就是 \((^{n - sz_u - y}_{sz_p - 1 - sz_u})\)，同时，我们还要考虑这 \((sz_p - 1) - sz[u]\) 个点加上点 \(p\) 的拓扑序数量，也就是我们上面提到的\(x = {cnt_p \over (^{sz_p - 1}_{sz[u]}) cnt_u}\)。于是，我们就有了 \(f_{u, x} = \sum_{y < x} (^{n - sz_u - y}_{sz_p - 1 - sz_u}) \times {cnt_p \over (^{sz_p - 1}_{sz[u]}) cnt_u} \times f_{p, y}\)。在我们实现的过程中，可以用前缀和优化，即 \(f_{u, x + 1} = f_{u, x} + (^{n - sz_u - x}_{sz_p - 1 - sz_u}) \times {cnt_p \over (^{sz_p - 1}_{sz[u]}) cnt_u} \times f_{p, x}\)
然后这个题就做完了。
void dfs(int cur, int p) {i64 ord = cnt[p] * inv(C(sz[p] - 1, sz[cur]) * cnt[cur] % Mod) % Mod;for (int i = 1; i + sz[cur] <= n + 1; ++i) {f[cur][i] = f[cur][i - 1];i64 add = C(n - sz[cur] - (i - 1), sz[p] - 1 - sz[cur]) * ord % Mod * f[p][i - 1] % Mod;(f[cur][i] += add) %= Mod;}for (auto &to : adj[cur]) {dfs(to, cur);}return;
}
ICPC Senyang
E
最多 16 种状态，将每个状态对应一个 2 进制位，就可以将所有的初态都压缩成一个 16 位二进制数。以这个二进制数为节点，操作为边代价为边权就可以得到一张图，要求的就是所有点到状态 0 的最短距离，所以我们建反图，求状态 0 到所有点的最短距离。
建图：
std::vector<std::array<int, 2>> op;op.emplace_back(std::array<int, 2>{ 1, a });op.emplace_back(std::array<int, 2>{ 2, a });op.emplace_back(std::array<int, 2>{ 4, a });op.emplace_back(std::array<int, 2>{ 8, a });op.emplace_back(std::array<int, 2>{ 3, b });op.emplace_back(std::array<int, 2>{ 12, b });op.emplace_back(std::array<int, 2>{ 5, c });op.emplace_back(std::array<int, 2>{ 10, c });op.emplace_back(std::array<int, 2>{ 15, d });// 枚举初态for (int i = 1; i < (1 << N); ++i) {// 枚举操作for (auto &[o, val] : op) {int v = 0;// 计算次态for (int j = 0; j < 16; ++j) {if (!(i >> j & 1)) {continue;}int nxt = j ^ o;if (nxt != 15) {v |= (1 << nxt);}}// 建反图adj[v].emplace_back(std::array<int, 2>{ i, val });}}// 然后跑 dijkstra
M
很容易想到把问题转换成图，但是一个问题是如何判断所有的强连通分量中是否存在非 0 环，若存在则只要进到这个强连通分量就能达到无限集，否则就只能循环几个数。我们考虑一个强连通分量中全部都是 0 环的情况，我们设立一个起点，则从起点以任意简单路径到一个点的距离应该相等（因为只有 0 环），所以我们直接从起点开始dfs，计算到每个点的距离，如果在 dfs 过程中发现一个点已经访问过且两次访问的距离不同，则说明存在非 0 环。
// id 是当前检查的强连通分量的编号
bool chk(int cur, int id, i64 v) {if (vis[cur]) {return hv[cur] == v;}hv[cur] = v;vis[cur] = true;bool ok = true;for (auto &[to, val] : adj[cur]) {if (scc[to] != id) {continue;}ok &= chk(to, id, v + val);}return ok;
}