我头上有鸡脚 鸡脚（待完坑）

· · 学习·文化课

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)}
  • $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} 的上下界限制。\ 考虑转移：

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，转移是容易的。\

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)。