——小熠《所以我戴上了耳机》
卡点更博。
506 ARC136F Flip Cells
这不是我们 ZJOI 的开关吗，没想到在这里看见了，下次转载记得标明出处捏。
首先，“第一次”这一限制采取经典的“走回容斥”进行转化，我们设 \(F(x)\) 表示在 \(n\) 步第一次到达终止态的概率，\(G(x)\) 表示 \(n\) 步到达终止态的概率，\(H(x)\) 为从终止态 \(n\) 步重返的概率，那么有：
考虑如何计算 \(G(x)\) 与 \(H(x)\)，两类计算是类似的，我们以 \(H(x)\) 为例。
一个暴力的想法是枚举所有最终状态，之后我们只关心有多少个格子被翻了奇数遍，作出类似 \((\frac{e^x-e^{-x}}{2})^k(\frac{e^x+e^{-x}}{2})^{hw-k}\) 的贡献。
我们事实上可以做一个暴力的 dp 计算出合法最终态被翻奇数次格子数量的分布 \(g_k\)，于是答案可被表示为：
注意我们卷积 \(G,H\) 时的合并并不是 EGF 合并形式，我们需提前作变换 \(\sum\frac{f_kx^k}{k!}\rightarrow\sum f_kx^k\)，注意到我们可以将上面的多项式拆为 \(\sum c_ie^{ix}\) 形式，我们可以独立地将每个 \(e^{ix}\) 变换为 \(\frac{1}{1-ix}\)。
但由于 \(G,H\) 内含有 \(\frac{1}{1-x}\) 项不能直接带入 \(x=1\)，两边乘上 \(1-x\) 再计算即可，复杂度 \(O((hw)^2)\)。
507 P7728 旧神归来（Return of Them）
首先我们只关心叶子深度的可重集 \(F(x)\)，手玩操作 \(x^d\) 后的影响：\(F(x)\rightarrow F(x)-x^d+x^dF(x)\)。
接着手玩更多次操作的影响，能写出：\(F(x)\rightarrow(F(x)-1)\prod(1+x^i)^{g_i}+1\)，其中 \(g_i\) 为深度为 \(i\) 的叶子操作次数。
于是在无限次操作后，我们会消去所有深度有限的叶子，得到：
先算出右边，左边从小到大 \(O(n\log n)\) 解出即可，复杂度 \(O(n\log n)\)。
508 2021 集训队互测 Round 3 T1 Lovely Dogs
这一函数有着较为经典的反演形式：
我们先考虑树是菊花的情况，即求 \(\sum_{i,j}f_d(a_ia_j)\)。增量地加入各个 \(a_i\)，可以写出贡献：
我们尝试将 \(k\) 的枚举约束在 \(a_i\) 因子范围内，注意到若 \(k\) 不为 \(a_i\) 因子且 \(k^{d+1}\mid a_j\)，这样的 \(j\) 不会与任何数产生贡献，可以直接忽略掉，于是每次加入数时在因子位置计入贡献即可做到 \(O(n\log n)\)。
树的情况在上面套一层 dsu on tree 就好了，重儿子继承贡献数组，轻儿子暴力枚举因子产生贡献，复杂度 \(O(n\log^2 n)\)。
509 2021 集训队互测 Round 3 T2 Alice、Bob 与 DFS
手玩与归纳可以发现每个点属于四种状态——先手/后手能控制结束时的先后手，先后手不变/交换，但这一方法并不适用于计算 SG 函数。
我们可以通过从起点开始的一条链刻画当前状态，为了记录更少的信息量，考虑一条链和单独链尾结点 \(t\) 的区别，事实上我们只是多出了弹空整个 \(t\) 这一种决策
马上写
510 2021 集训队互测 Round 3 T3 音符大师
dp，记录一下控制上次音符的手位置，线段树维护另一只手，但是这只能做到 \(O(nL^2\log n)\)。
增量地一步步转移并不适用于所有的题目，我们尝试使用跳跃的刷表法。注意到我们永远能用某个 \([a_i-L,a_i]/[a_i,a_i+L]\) 以及 \([j,j+L]\) 来刻画当前状态，尝试对于当前区间找到之后第一个不在区间内的位置 \(x\)（倒着加数即可维护），并分讨这一步动哪只手：
- 若移动 \(a_i\) 对应区间，那么相当于全局加再线段树合并（注意这里合并的树形结构）；
- 若移动 \(j\) 对应区间，向后找一个 \(j\) 也同时不包含的点做个单点修改即可。
可以说明以上策略能包含最优策略，于是线段树维护即可，复杂度 \(O(nL\log n)\)。