最近……唉不说了。很久没有写题目总结了呢。
CF804F Fake Bullions
分为两个部分求解。
Part I
Task：求出每个帮派最小和最大售出的金条数量。
最小值 \(mn_i\) 显然即为在初始状态下拥有的真金条的数量，重点是考虑最大值 \(mx_i\)，其显然等于在尽可能地进行传递后帮派拥有的金条总数量。
Lemma 1：对于一条边 \(u\rightarrow v\)，当且仅当满足 \(i\equiv j \pmod{\gcd(s_u,s_v)}\) 时，\(u\) 点内的第 \(i\) 个元素会 copy 一份假金条给 \(v\) 点内的第 \(j\) 个元素。
Lemma 2：考虑令 \(f(v, g)\) 表示一个大小为 \(g\) 的帮派，满足 \(g \mid s[v]\)，且当且仅当 \(v\) 帮派的 \(j\) 号元素拥有金条，\(i\equiv j\pmod{g}\) 时，该帮派中的元素 \(i\) 拥有金条。对于 \(u\rightarrow v\)、\(v\rightarrow w\) 两条边，\(u\) 对 \(w\) 的影响等同于 \(f(u, \gcd(s_u, s_v))\) 对 \(w\) 的影响。
Lemma 3：考虑一条路径 \(u_1\rightarrow u_2\rightarrow \dots \rightarrow u_n\)，\(u_1\) 对 \(u_n\) 的影响为 \(f(u_1,\gcd(s_{u_1},s_{u_2},\dots,s_{u_n}))\) 对 \(u_n\) 的影响。
Lemma 4：考虑一个由 \(u\) 出发的简单环 \(u\rightarrow v_1\rightarrow v_2\rightarrow\dots\rightarrow v_n\rightarrow u\)，令 \(w=f(u, \gcd(s_{v_1},s_{v_2},\dots,s_{v_n}))\)，则可以声称，\(mx_u=\frac{s_u}{s_w} \cdot mx_w\)。
综合以上推论，可以对原图的所有强连通分量缩点，考虑单个强连通分量内的点 \(a_1,a_2,\dots,a_n\)，可以简单地统计分量内部的影响：令 \(g=\gcd(a_1,a_2,\dots,a_n)\)，点 \(v\) 的第 \(i\) 个元素拥有金条当且仅当存在 \(j\) 使得 \(f(a_j,g)\) 的第 \(i\) 个元素拥有金条。
对于强连通分量之间的贡献，考虑到缩点后的图为一个有向无环竞赛图，可以简单地在拓扑序上进行 DP 计算这部分贡献。
Part II
Task：求解集合种类数。
枚举一个帮派，钦定它为选上的 \(b\) 个帮派中权值最小的，考虑比较其他帮派和钦定帮派的 \(mx\)：
- 若 \(mn_v>mx_u\)，始终会被选上，设共有 \(p\) 个。
- 若 \(mx_v<mn_u\)，不可能被选上，设共有 \(q\) 个。
- 否则既可以选也可以不选。
因此答案为：