被树上的数打爆了，滚来写没有黑题的NOIP2020。
排水系统
题意：给定一张DAG，任意点度数不超过 \(5\)。
\(m\) 个点有初始容量 \(1\)，一个点的容量会平均流给每条出边，求所有汇点的最终容量。
数据范围：\(1 \le n \le 10^5,\ 1 \le m \le 10\)，保证任意一条源点到汇点的路径长不大于 \(11\)。
估算一下最后答案的量级：
对于分母，由于每个 \(1\) 至多被除 \(11\) 次 \(x\)，上界应为 \(\text{lcm}(5^{11},4^{11}, 3^{11}, 2^{11}, 1^{11}) = 60^{11}\)。
分子不会超过 \(10\) 倍分母。因此可以简单的用 i128 维护，做一遍拓扑排序即可。
字符串匹配
题意：定义 \(F(A)\) 表示串 \(A\) 中出现次数为奇数的字符个数。
给定 \(S\)，求 \(S = (AB)^kC\) 的拆分个数，满足 \(A, B, C\) 都不为空，且 \(F(A) \le F(C)\)。
数据范围：\(\vert S\vert \le 2^{20}\)。
求出串 \(S\) 的失配指针，根据经典结论，前缀 \(i\) 的最小正周期为 \(i - fail(i)\)。
枚举前缀 \(i\) 作为 \(AB\)，当且仅当 \(k \times i\) 的最小正周期能整除 \(i\)，\(k \times i\) 能被表示为 \((AB)^i\)。
预处理 \(p_i\) 表示前缀 \(i\) 的奇字符个数，同样求出 \([i, n]\) 的信息 \(s_i\)。
问题转化为：有多少个 \(j \in [1, i)\) 满足 \(p_j \le s_{k \times i + 1}\)。
此处用主席树复杂度就爆炸了，注意到 \(s_i \le 26\)，那么统计 \(f(i, k) = \sum_{j \le i} [p_i \le k]\) 即可。
时间复杂度 \(O(26n + n \ln n)\)。
微信步数
题意：\(m\) 维平面，第 \(i\) 维值域为 \([1, w_i]\)。
现在从某个起点开始走，\(n\) 步操作，第 \(i\) 步会使当前第 \(c_i\) 维的坐标加 \(d_i \in \{-1, 1\}\)。
重复 \(n\) 步操作直到走出平面。求所有 \(\prod w\) 个起点的最终路径长度和。
数据范围：\(1 \le n \le 5 \times 10^5,\ 1 \le m \le 10\)。
枚举步数，求出还没死的起点个数，即当前步对答案的贡献。
如果判断一个点死没死？由于有一维死整个都死，不妨按维考虑。
设 \([l_i, r_i]\) 表示第 \(i\) 维的历史最小/大位移，一个起点存活当且仅当 \(\forall 1\le i \le m,\ x_i \in[1 - l_i, w_i - r_i]\)。
反过来说当前没死的节点个数等于 \(\prod (w_i - r_i + l_i)\)。
容易写出 \(O(Tnm)\) 的暴力，其中 \(T\) 表示最大循环轮数（\(1 \sim n\) 被称为一轮）。
如果一轮过后回到起点，且有节点存活，则输出 \(-1\)。
int inf = 1;
while(1) {
for(auto [c, d] : op) {
e[c] += d;
l[c] = min(l[c], e[c]), r[c] = max(r[c], e[c]);
if(r[c] - l[c] >= w[c]) {
cout << ans;
exit(0);
}
ll s = 1;
for(int j = 1; j <= m; ++ j) {
s = s * (w[j] - r[j] + l[j]) % mod;
}
ans = (ans + s) % mod;
}
if(inf) {
for(int i = 1; i <= m; ++ i) {
if(e[i]) {
inf = 0;
break;
}
}
if(inf) return cout << -1, 0;
}
}
考虑第 \(j\) 维：
在第一轮第 \(i\) 步时，历史移动最大位移为 \([l_i, r_i]\)，死了 \(r_i - l_i\) 个点。
设一轮的总偏移量为 \(e_j\)，则第二轮第 \(i\) 步的历史最大位移更新为 \(\left[\min(l_n,\ e_j + l_i),\ \max(r_n,\ e_j + r_i)\right]\)。
\(1 \sim i\) 中新增死亡人数等于 \(\max(0, l_n - e_j - l_i) + \max(0, e_j + r_i - r_n)\)，记作 \(f_{i, j}\)。
容易发现以下事实：除开第一轮，第二、三……轮每步的死亡情况是一致的。
设第一轮过后还活着 \(a_j\) 个节点，接下来每轮过后会有 \(b_j\) 个起点死亡，最后一轮的 \(1 \sim i\) 步死了 \(f_{i, j}\) 个节点。
那么对于第 \(x + 2\) 轮的第 \(i\) 步，剩余存活点数等于 \(a_j - x b_j - f_{i, j}\)。
所有维度的存活点数都必须大于 \(0\)，显然有阈值 \(T_i = \min \lfloor\frac{a_j - f_{i, j}}{b_j}\rfloor\)，\(x\) 从 \(0\) 枚举到 \(T\)。
由于最后一轮不一定走完，可能存在一个 \(k\)，使得 \(T_{i < k} = T_{i \ge k} + 1\)。
\[\sum_{i = 1}^n \sum_{x = 0}^{T_i}\prod_{j = 1}^m (a_j - xb_j - f_{i, j}) \]后面是个 \(m\) 次多项式，\(O(m^2)\) 求出各项系数。
拆成 \(m + 1\) 个单项式 \(p_jx^j\)，分别算 \(p_j\sum_{x = 0}^Tx^j\)，这是关于 \(T\) 的 \(j + 1\) 次多项式，插值法解决。
这样可以 \(O(j)\) 求出点值，时间复杂度 \(O(nm^2)\)。
移球游戏
题意：
标签：11,10,le,题意,sum,times,NOIP2020 From： https://www.cnblogs.com/Luxinze/p/18472988