CF901D
抽出一棵生成树，可以满足除了根结点以外的值。
考虑非树边 \((u,v)\)，如果构成偶环，则没有影响。
如果构成奇环，那么如果对于环 \(\pm 1\)，根节点的影响是 \(\pm 2\)，判断一下合法性即可。
CF1616H/qoj4431
对 \(a\) 建 Trie，设 \(f_u\) 表示在 \(u\) 子树内选数的方案数。发现转移需要用到 \(g_{x,y}\) 表示在 \(x,y\) 子树内各选非0个数合法的方案。那我们不妨把 \(f_u\) 变成 \(g_{u,u}\) 来表示。
考虑 \(g_{x,y}\) 的转移，如果 \(k\) 在当前位为 \(0\)，那么 \(g_{x,y}=g_{ls(x),ls(y)}+g_{rs(x),rs(y)}\)。
否则，令 \(s_u=2^{siz_{u}}-1\)，分讨：
- \(x=y\)，\(g_{x,x}=g_{ls(x),rs(x)}+s_{ls(x)}+s_{rs(x)}\)
- \(x\ne y\)，\(g_{x,y}=\)
\(s_{ls(x)}s_{ls(y)}+s_{rs(x)}s_{rs(y)}\)：\(x,y\) 都只在同侧选。
\(g_{ls(x),rs(y)}+g_{rs(x),ls(y)}\)：\(x,y\) 选了相反的子树。
\(g_{ls(x),rs(y)}(s_{rs(x)}+s_{ls(y)})+g_{ls(y),rs(x)}(s_{rs(y)}+s_{ls(x)})\)：一边两个子树都选，一边只选一个子树。
\(g_{ls(x),rs(y)}g_{ls(y),rs(x)}\)：四个子树都选。总复杂度 \(O(n\log V)\)。
CF1830D
考虑一开始先把所有贡献按照 \(\mathrm{mex}=2\) 算，然后通过树形 dp 减去最小的贡献。
设 \(f_{u,i,0/1}\) 表示 \(u\) 所在连通块颜色为 \(0/1\)，大小为 \(i\)。转移是容易的，\(O(n^2)\)。
考虑优化。注意到，如果我们交替染色，那么损失量为 \(1.5n\)，这给了一个很好的上界。对于 \(f_{u,i,0/1}\)，其损失量至少为 \(i(i-1)/2+n-i\)，于是 \(i\le \sqrt n+1\)。复杂度 \(O(n\sqrt n)\)。
P8885
定义奇串为：有奇数个本质不同子序列（包含空子序列）的串。
定义好串为：有奇数个子串是奇串的串。这等价于其所有子串的的本质不同子序列个数之和为奇数。
考虑奇串的判定：设 \(f_{i,c}\) 表示以 \(c\) 结尾的子序列（非空）个数，那么 \(f_{i,a_i}=f_{i-1,0}+f_{i-1,1}+1\)，\(f_{i,1-a_i}=f_{i-1,1-a_i}\)。
先滚动数组，于是 \(i\) 这一维我们先去掉。
考虑引入 \(f_U=f_0+f_1+1\)，表示全部的子序列个数，在模 2 意义下，加入 \(x\) 后，变化如下：
- \(f_x=f^{\prime}_U\)
- \(f_U=f^{\prime}_U+f^{\prime}_{1-x}+1=2f^{\prime}_U-f^{\prime}_x=f^{\prime}_x\)
发现是交换 \(f_x,f_U\)。对于初始状态，\(f_U=1,f_{0/1}=0\)，于是满足只会存在一个 1。
考虑好串的判定：那么我们对于串扫描线，记录当前以 \(i\) 结尾的字串有多少个是 \(f_{U/0/1}=1\) 的，并记录奇串个数 \(tot\)，这些都可以在 \(\bmod 2\) 意义下记录，于是共有 16 种状态。
考虑带?的情况：我们需要分别记录上述 16 种状态分别有多少个，dp 即可。
考虑子串查询：这个 dp 就是可以写成是一段矩阵的乘积，那么考虑猫树分治，复杂度 \(O(16^2 (n\log n+q))\)
CF1456E
这个题怎么一直纠缠我。
先考虑单个数的上下界 \(l\le x \le r\) 限制。首先 \(l,r\) 的 lcp 部分 \(x\) 是固定的。然后 lcp 之后，如果选了 \(0\)，那么脱离了 \(r\) 的限制，如果选了 \(1\)，那么脱离了 \(l\) 的限制。之后只需要考虑一个的限制，最后这个限制会在某个时刻消失。
考虑一个贪心，如果我们知道 \(i\sim j\) 这个区间内最晚完全解除限制的位，那么往下的位置可以随便选。
于是我们可以设计一个区间 dp，\(f_{i,j,d,0/1,0/1,0/1,0/1}\)，表示区间 \([i,j]\) 都已经脱离了限制，考虑了 \(\ge d\) 的数位，\(x_{i-1}\) 的上下界限制，\(x_{j+1}\) 的上下界限制。
考虑转移：
- \([i,j]\) 不存在第 \(d\) 位脱离限制的：从 \(f_{i,j,d+1,\cdots}\) 转移过来，要加上第 \(d\) 位的贡献。
- \([i,j]\) 存在 \(x_k\) 在第 \(d\) 位脱离限制的：从 \(f_{i,k-1,d+1,\cdots}+f_{k+1,j,d+1,\cdots}\) 转移过来，也要加上第 \(d\) 位的贡献。
CF1500F
qoj2210
P10107
考虑使用 bfs 将点标号，对于 \(u\) 子树内同一层的节点的 bfs 序标号是连续的。
一些记号：
- 设 \(L_{u,i}\) 表示 \(u\) 子树内深度为 \(i\) 的编号最小的点。
- 右侧点集：\(u\) 子树内深度为 \(i\) 的右侧点集为 \(R_{u,i}=\{v|dep_v=i,i\ge L_{u,i}\}\)
- 右下方点集：\(u\) 的右下方点集为 \(D_u=\cup_{i=dep_u} R_{u,i}\)。
- 把原本的点权用 \(a\) 数组表示。
预处理数组 \(cnt_{u,i}\) 表示 \(\sum_{v\in D_{u}} \left\lfloor\frac{a_v}{2^i}\right\rfloor\bmod 2\)，转移是容易的。
\(sum_{u,i}\) 表示 \(D_u\) 中 \(2^i\) 层以内的答案，容易用 \(cnt\) 求出。查询的时候倍增跳即可，查询的点的编号为一段区间，复杂度为 \(O((n+q)\log V)\)。
P10084
考虑 \(F(x,a,b)\) 是多少？通过辗转相除法，不妨设 \(a\le b\)，则 \(x^b-1 \bmod x^a-1=x^b-1-x^{b-a}(x^a-1)=x^{b-a}-1\)，于是最后得到 \(x^{\gcd(a,b)}-1\)，再加一就变成 \(x^{\gcd(a,b)}\) 了。问题转化为求 \([1,km]\) 的答案。
列出生成函数，我们求 \([x^0]\prod_{i=1}^{km} (x^i+1)\bmod x^m-1\)。
注意单位根反演：\([m|i]=\frac{1}{m}\sum_{k=0}^{m-1}\omega_m^{ik}\)。
设 \(f(x)=\prod_{i=1}^{km}(x^i+1)\)，答案为 \(\frac{1}{m}\sum_{i=0}^{m-1}f(\omega_{m}^{i})\)。
注意到 \(z^m-1=\prod_{i=0}^{m-1}(z-\omega_m^i)\)，代入 \(z=-1\) 得到 \(\prod_{i=0}^{m-1} (\omega_m^i+1)=2(m\bmod 2)\)。
设 \(i|m\)，且 \(m/i\) 是奇数，于是 \(f(\omega_m^i)=2^{ki}\)。原式等于 \(\frac{1}{m}\sum_{i|m,m/i\bmod 2=1} 2^{ki}\varphi(m/i)\)。