CF Round 942(#1967) 总结
A
\(cnt\) 为 \(\min\{a\}\) 的个数，则答案为 \(cnt\times \min\{a\}+(n-cnt)\times (\min \{a\}+1)\)。
于是把 \(K\) 尽量往小的补齐即可。
B1
存在整数 \(p\) 使得 \(a+b=p\times b\times \gcd(a,b)\)。移项得 \(\frac ab+1=p\times \gcd(a,b)\)。
则 \(a\) 是 \(b\) 的倍数，调和级数枚举再 \(O(\log n)\) check 即可，复杂度 \(O(n\log ^2n)\)。
B2
令 \(d=\gcd(a,b),a=a'd,b=b'd\)。将原来的条件两边除以 \(d\)，得到 \((a'+b')|(b'd)\)，且要满足 \(\gcd(a',b')=1\)。
有欧几里得定理，\(\gcd(a'+b',b')=\gcd(a',b')=1\)，再由 \((a'+b')|(b'd)\) 所以只能是 \((a'+b')|d\)。
那么 \(a'\le d=\frac a a'\le \frac na'\)，所以 \(a'^2\le n\)。同样地，\(b'^2\le m\)。
那么枚举 \(a',b'\) 计算 \((a'+b')\) 在范围内倍数的个数即可。复杂度 \(O(\sqrt {nm})\)。
C
可以把每个点 \(a(0)\) 对其祖先 \(a(k)\) 的贡献拆开来，那么一个点对它的 \(dep\) 级祖先（从 \(1\) 开始）的 \(a(k)\) 贡献 \(a(0)\times \binom {dep+K-1}{K-1}\)。
由于叶子始终是 \(a(0)\) 那么自底向上求出每个点的 \(a(0)\) 即可。由于树高是 \(O(\log n)\) 的，所以组合数可以暴力求，更新也可以暴力更新。
复杂度 \(O(n\log ^2n)\)。
D
每个位置的修改都是独立的，我们只要使每个位置修改次数的最大值最小，考虑二分答案。然后贪心地，从前往后依次使每个 \(a\) 取到 \(mid\) 步内能取到的最小值，且要使 \(a_i\ge a_{i-1}\)。
一种想法是求出 \(mid\) 步路径上的最小值，复杂度是两个 $\log $，难写且过不了。
考虑到 \(a_i\) 是不下降的，我们维护一个头指针 \(x\)，每次把 \(x\) 往右移，check \((x,i)\) 是否 \(\le mid\) 即可。
要 check 是否在同一个基环树中并且树上是否是祖孙关系，\(O(m\log m)\) 预处理 LCA 即可。环上距离和书上距离都是容易的。
总复杂度 \(O((n+m)\log m)\)。
E1 & E2
假如当前走到 \(b_i=at\)，那么当 \(a_{i+1}=at+1\) 时，\(b_{i+1}=at-1\)；否则 \(b_{i+1}=at+1\) 一定更优。所以每次往上走有 \(m-1\) 的系数，往下走有 \(1\) 的系数。走到 \(m\) 或 \(-1\) 以后就不用走了。直接 DP 可以做到 \(O(nm)\)。
考虑计算不合法的方案数，如果我们第一次走到了 \((i,-1)\)，那么后面可以乱填 \(m^{n-i}\) 种，这其实等价于后面继续走，依然是往上走 \(m-1\) 系数，往下走 \(1\) 系数，求和后依然是 \(m^{n-i}\) 种。所以枚举最后走到 \((n,p)\) 计算走到过 \(y=-1\) 时的方案数。
- 当 \(p\le -1\) 时，一定会经过 \(y=-1\)。
- 当 \(p>-1\) 时，利用类似格路计数的，反射一次转化为 \(p\le -1\) 的情况。
反射容斥。记 \(X\) 为碰到上边界，\(Y\) 为碰到下边界，\(f(S)\) 表示计算 \(S\) 作为实际状态的子序列时的方案数，要计算 \(f(Y)-f(XY)+f(YXY)-f(XYXY)+\cdots\)。计算一个点的方案数时，记向上走了 \(k\) 次，贡献为 \((m-1)^k\binom nk\)。
发现反射后的各点其实是 \(p,-p+2m,p-2m-2,-p+4m+2,\dots\)。奇数项是 \(p\) 开头、公差 \(-2m-2\) 的等差数列，偶数项是 \(-p+2m\) 开头、公差 \(2m+2\) 的等差数列。代入到贡献里就是（以奇数项为例）：
注意这里系数恒为 \((m-1)^{(n+p-b)/2}\)，因为我们实际上还是走到 \((n,p)\)。我们可以维护 \(\sum c_i\binom{n}i\) 的系数 \(c_i\)，上述贡献就是在 \(c\) 上每 \(m+1\) 间隔加上系数。用类似差分的方式处理，最后扫一遍 \(c\) 即可。复杂度 \(O(n+m)\)。