2023.5-526互联

ARC157D

绷不住了

设行切了 \(x\) 刀，列切了 \(y\) 刀，Y 的总数为 \(A\)，那么需要有 \(2(x+1)(y+1)=A\)。

进一步，如果确定了 \(x,y\)，那么行被分成的这 \(x+1\) 部分中一定每一部分都恰好有 \(2(y+1)\) 个 Y。再进一步，对于每一种符合这个条件的行的分割方案，他们对应的列的分割方案数都是相同的。

容易在 \(O(H+W)\) 的时间内对一组 \(x,y\) 算出方案；最后需要 check 一下方案是否合法，预处理二维前缀和后枚举每一块判断就行了。

复杂度是 \(O((H+W+A)d(A))\)，其中 \(d\) 分别表示约数个数。由于 \(d(A)\le \sqrt[3]{A}\) 因此很稳。

ABC282H

分治。算出分治中心到左右的最小值 \(A_i,B_i\) 与和 \(C_i,D_i\)，那么相当于要求

\[\min(A_i,C_i)+B_i+D_i\le S \]

分类讨论，若 \(A_i\le C_i\) 相当于 \(D_i\le S-A_i-B_i\)，否则相当于 \(C_i+D_i\le S-B_i\)。

典型的二维偏序模式，平衡树/权值线段树维护，总复杂度 \(O(N\log ^2N)\)。

ABC282G

\(f(i,l,j,k)\) 表示填了前 \(i\) 个数，\(A_i=j,B_i=k\)，目前有 \(l\) 个 \((A_{i+1}-A_i)(B_{i+1}-B_i)>0\) 的方案数。转移考虑上一个 \(A_{i-1}=x,B_{i-1}=y\)，用 DP-T 的技巧平移一下，分四种情况讨论即可。

二维前缀和优化即可。复杂度 \(O(N^4)\)。

CF17-Final J

Boruvka 之后变成：对每个点求出他到其他集合中某个点的最小距离。

做一遍换根 DP 即可，DP 的时候需要记录距离当前点最小的距离及其颜色 \(c\)，和颜色 \(\neq c\) 中的最小距离。总复杂度 \(O(N\log N)\)。这怎么都评 Silver 啊？

20230502

链加子树和 1log。

转成 \(\sum_{v\in\text{subtree}(u)}\text{mark}(v)\times (\text{dep}(v)-\text{dep}(u))\)，两个线段树维护。

P4587

很典的题，一年前口胡了但是没写。

考虑朴素算法：从小到大考虑所有 \(a_i\)，设当前答案为 \(x\)，若 \(a_i\le x+1\) 则 \(x\leftarrow x+a_i\)，否则答案为 \(x+1\)。考虑优化，发现只需要每次把上一个 \(a_i\) 到当前 \(x+1\) 的所有数一起加，这样答案至少增倍；使用主席树维护，由于答案不超过 \(\sum a_i\) 故总复杂度 \(O(n\log n\log \sum a_i)\)。

空间复杂度是 \(O(n\log V)\)，不过离线下来一起跳就可以做到线性了。orz cftm

ABC248Ex

提供一个 \(O(N\log ^2N)\) 的做法，不依赖于 \(0\le K\le 3\) 这一限制。

考虑分治，对于「\([l,r]\) 有多少个子区间符合条件」这一问题，取 \(m=\lfloor\frac{l+r}{2}\rfloor\)，算出跨过 \(m\) 的区间个数，把被 \([l,m],[m+1,r]\) 包含的区间看成子问题分治下去。

设 \(a_i,b_i,c_i,d_i\) 表示左右两侧距离为 \(i\) 的最大值与最小值，那么条件合法当且仅当

\[\max(a_i,c_j)-\min(b_i,d_j)\le i+j+K-1 \]

枚举 \(i\)，钦定 \(a_i\ge c_j\) 即 \(\max(a_i,c_j)=a_i\)，分两种情况讨论：

若 \(b_i\le d_j\)，则要求 \(a_i-b_i-i-K+1\le j\)
若 \(b_i>d_j\)，则要求 \(a_i-i-K+1\le j+d_j\)

注意到 \(a,c\) 均单调递增，\(b,d\) 均单调递减，因此 \(a_i,b_i\) 那两维的约束都可以表示成「\(j\) 在某个区间内」这样的约束。这样就只有两维数点了，可以做到 \(O(N\log N)\)。总复杂度 \(O(N\log ^2N)\)。

CTSC2006 歌唱王国

设最后的序列长度为 \(X\)，这是一个随机变量。考虑其期望

\[\mathbb E[X]=\sum_{i=0}^{\infty }\text{Pr}[X=i]\times i=\sum_{i=0}^{\infty}\text{Pr}[X>i] \]

因此，如果设 \(F(x)\) 是 \(X\) 的 PGF，\(G(x)\) 是 \(g_i=\text{Pr}[X>i]\) 的 OGF，就有 \(F'(1)=G(1)\)。

另一方面，考虑以下事件发生的概率：在 \(T\) 次随机之后，仍然没有结束，接下来不管是否结束都新加入 \(m\) 个字符，且他们恰好为 \(S\) 的概率。不难发现这是 \(g_{T}\times \frac{1}{n^m}\)。

另一方面，这种情况下实际的结束时间 \(X'\) 一定在 \([T+1,T+m]\) 之间，考虑 \(\text{Pr}[X'=T+i]\)（这里使用 \(X'\) 而非原来的 \(X\)，是因为这个变量和原来的变量并不相同），发现首先要在 \(T+i\) 时刻结束，第二要满足 \(S[1\cdots i]=S[m-i+1\cdots m]\)，第三要满足后面那些刚好凑上 \(S\)。

不难发现这三个也是充分条件。

因此，\(\text{Pr}[X'=T+i]=\text{Pr}[X=T+i]\times \text{isborder}(i)\)。有

\[\begin{aligned}g_T\times\dfrac{1}{n^m}&=\sum_{i=1}^mf_{T+i}\times\text{isborder}(i)\times\dfrac{1}{n^{m-i}}\\\iff [\dfrac{x^T}{n^m}]G(x)&=\sum_{i=1}^m\text{isborder}(i)\times [\dfrac{x^{T+i}}{n^{m-i}}]F(x)=\sum_{i=1}^{m}\text{isborder}(i)\times[\dfrac{x^{T+i}}{n^{m-i}}]\dfrac{F(x)}{x^i}\\\iff \dfrac{1}{n^m}\times x^mG(x)&=\sum_{i=1}^m\text{isborder}(i)\times x^{m-i}F(x)\times \dfrac{1}{n^{m-i}}\end{aligned} \]

将 \(x=1\) 带入即得 \(F'(1)=G(1)=\sum_{i=1}^m\text{isborder}(i)\times n^i\)。

变式

求随机变量 \(X\) 的方差。

考虑到方差即 \(\mathbb E[X^2]-(\mathbb E[X]^2)\)，有

\[\mathbb E[X^2]=\sum_{i=0}^{\infty}\text{Pr}[X=i]\times i^2=\sum_{i=0}^{\infty}\text{Pr}[X=i]\times i(i-1)+\sum_{i=0}^{\infty}\text{Pr}[X=i]\times i\\=F''(1)+F'(1) \]

因此方差即 \(F''(1)+F'(1)-(F'(1)^2)\)。考虑 \(F''(1)\) 咋算，由 \(f_i=g_{i-1}-g_i,f_0=0\) 可得

\[[x^i]F(x)=[x^{i-1}]G(x)-[x^i]G(x)\qquad(i>0)\\ F(x)=xG(x)-(G(x)-1)\iff F(x)+G(x)=xG(x)+1 \]

两边求二阶导有

\[F'(x)+G'(x)=xG'(x)+G(x)\\ F''(x)+G''(x)=xG''(x)+G'(x)+G'(x) \]

取 \(x=1\)，有 \(F''(1)=2G'(1)\)；另一方面，由

\[x^mG(x)=\sum_{i=1}^m\text{isborder}(i)\times x^{m-i} F(x)\times n^i \]

两边求导有

\[mx^{m-1}G(x)+x^mG'(x)=\sum_{i=1}^m\text{isborder}(i)\times (x^{m-i}F'(x)+(m-i)x^{m-i-1}F(x))\times n^i \]

带入 \(x=1\) 即得

\[G'(1)=-mF'(1)+\sum_{i=1}^m\text{isborder}(i)\times (F'(1)+m-i)\times n^i\\ F''(1)=2G'(1)=2\sum_{i=1}^m\text{isborder}(i)\times (F'(1)-i)\times n^i \]

2018 年集训队论文指出

\[F^{(k)}(1)=k\cdot\sum_{i=1}^ma_in^i\sum_{j=0}^{k-1}(-1)^j\binom{k-1}{j}\dfrac{(i+j-1)!}{(i-1)!}F^{(k-1-j)}(1) \]

其中 \(a_i=\text{isborder}(i)\)。该结论容易通过归纳得出。具体地，我们把以下二式同时求 \(k\) 阶导

\[F(x)+G(x)=xG(x)+1\\ G(x)=\sum_{i=1}^m\text{isborder}(i)\times x^{-i} F(x)\times n^i \]

即可得到上式。

ABC241Ex

考虑随便选的时候（即没有 \(B_i\) 这个约束）答案是啥，发现是（我应该没推错）

\[[x^M]\prod_{i=1}^N(1+A_ix+A_i^2x^2+\cdots)=[x^M]\prod_{i=1}^N\dfrac{1}{1-A_ix} \]

这东西......总之可以暴力算出 \(F(x)=\prod(1-A_ix)\)，然后求逆。

我不会多项式科技怎么办！只会暴力写求逆递推式然后矩阵快速幂 \(O(N^3\log M)\) 啊，自闭了。

考虑拆一手，待定系数

\[\begin{aligned}\prod_{i=1}^N\dfrac{1}{1-A_ix}&=\sum_{i=1}^N\dfrac{c_i}{1-A_ix}\\1&=\sum_{i=1}^Nc_i\prod_{j\neq i}(1-A_jx)\end{aligned} \]

依次取 \(x=A_1^{-1},A_2^{-1},\cdots,A_N^{-1}\)，我们就可以得到

\[c_i\prod_{j\neq i}(1-A_jA_i^{-1})=1\qquad(1\le i\le N) \]

这样就可以 \(O(N^2)\) 时间内解出 \(c_i\) 的值。接下来就有

\[[x^M]\prod_{i=1}^N\dfrac{1}{1-A_ix}=\sum_{i=1}^Nc_iA_i^M \]

然后考虑容斥，钦定 \(S\) 以内爆限制，发现只需要把 \(M\) 减去 \(\sum_{i\in S}B_i\) 然后乘上 \(\prod_{i\in S}A_i^{B_i}\) 就行了。

总的时间复杂度为 \(O(2^N\times N\log P)\)。

实际上你可以发现容斥干的事情无非是把原答案的多项式

\[[x^M]\prod_{i=1}^N\dfrac{1-A_i^{B_i+1}x^{B_i+1}}{1-A_ix} \]
的分子展开了而已！和生成函数做法没啥区别的！！

ABC241G

考虑 \(1\) 能不能成为 winner。显然应当先让 \(1\) 剩下的边全部都连向对面。设此时 \(1\) 的胜场数为 \(A\)。

现在算出来剩下所有点当前胜场数 \(x_i\)，相当于对每条未确定的边 \((u,v)\)，你要选择一个方向，然后让 \(x_u\leftarrow x_u+1\) 或者 \(x_v\leftarrow x_v+1\)。要求最后 \(x_i<A\)。

想了若干贪心都假了。

考虑网络流，设有 \(m\) 个未确定的边，建 \(n+m\) 个点，每个 \(1\le i\le m\) 向 \(u_i+m,v_i+m\) 连边，容量为 \(\infty\)，\(s\) 向 \(i\) 连边，容量为 \(w\)。每个 \(i+m\) 向 \(t\) 连边，容量为 \(A-x_i-1\)。最后满流就有解。

ABC240G

当 \(N<|X|+|Y|+|Z|\) 时无解。

否则，考虑先算出将 \(a\) 步分配到一个长为 \(b\) 的维度上，发现方案数是

\[\binom{a}{\frac{a+b}{2}} \]

不妨考虑两维的情况

\[\begin{aligned} F(N)&=\sum_{x=0}^N\binom{N}{x}\binom{x}{\frac{x+X}{2}}\binom{N-x}{\frac{N+Y-x}{2}}\\ &=\sum_{x=0}^N\dfrac{N!}{(\frac{x+X}{2})!(\frac{x-X}{2})!(\frac{N+Y-x}{2})!(\frac{N-Y-x}{2})!}\\ &=\dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N+X+Y}{2})!}\sum_{x=0}^N\dfrac{(N-X-Y)!(N+X+Y)!}{(\frac{x+X}{2})!(\frac{x-X}{2})!(\frac{N+Y-x}{2})!(\frac{N-Y-x}{2})!}\\ &=\dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N+X+Y}{2})!}\sum_{x=0}^N\binom{\frac{N-X-Y}{2}}{\frac{x-X}{2}}\binom{\frac{N+X+Y}{2}}{\frac{N+Y-x}{2}}\\ &=\binom{N}{\frac{N+X+Y}{2}}\binom{N}{\frac{N+X-Y}{2}} \end{aligned} \]

那么答案就是

\[\sum_{z=0}^NF(N-z)\binom{N}{z}\binom{z}{\frac{z+Z}{2}} \]

做完了。

写个 EGF：

\[f_X(x)=\sum_{n\ge 0}\dfrac{1}{(2n+X)!}\binom{2n+X}{n}x^{2n+X} \]
我草了，这个东西的封闭形式是 \(I_X(2x)\)，其中 \(I_{\alpha}\) 是第一类修正贝塞尔函数，好高深！

ABC226H

由于

\[\mathbb E[X]=\int_0^{\infty}\text{Pr}[X=i]\times i\text{ d}i=\int_0^{\infty}\text{Pr}[X>i]\text{ d}i \]

考虑使用 minmax 容斥，有

\[\begin{aligned} \mathbb E[\max\nolimits_K\{X_i|i=1,2,\cdots,N\}]&=\sum_{T}\binom{|T|-1}{|T|-K}(-1)^{|T|+K}\mathbb E\left[\min\nolimits_{i\in T}X_i\right]\\&=\sum_{T}\binom{|T|-1}{|T|-K}(-1)^{|T|+K}\int_{0}^{100}\text{Pr}[\min\nolimits_{i\in T}X_i> v]\text{ d}v\\ &=\int_{0}^{100}\sum_{T}\binom{|T|-1}{|T|-K}(-1)^{|T|+K}\prod_{i\in T}\dfrac{R_i-v}{R_i-L_i}\text{ d}v \end{aligned} \]

我们可以算出

\[f(v)=\sum_{T}\binom{|T|-1}{|T|-K}(-1)^{|T|+K}\prod_{i\in T}\text{Pr}[X_i>v] \]

考虑 \(\text{Pr}[X_i>v]\)，发现他是一个分段函数：

\[\text{Pr}[X_i>v]=\begin{cases}0&,v\ge R_i\\\dfrac{R_i-v}{R_i-L_i}&,L_i\le v<R_i\\1&,v<L_i\end{cases} \]

因此，最终的 \(f(v)\) 将是一个不超过 \(2N\) 段的分段函数，对每段分别计算并积分即可。

具体来说，\(f(v)\) 的每一段都可以表述为

\[\begin{aligned} &\int_{a}^b\sum_{i=K}^N\binom{i-1}{i-K}(-1)^{i+K}[x^i]\prod_{i=1}^N\left(1+(k_iv+b_i)x\right)\text{ d}v\\ =&\int_a^b\sum_{i=K}^N\binom{i-1}{i-K}(-1)^{i+K}g_i(v)\text{ d}v\\ =&\sum_{i=K}^N\binom{i-1}{i-K}(-1)^{i+K}\int_{a}^bg_i(v)\text{ d}v \end{aligned} \]

其中，\(g_i(v)=[x^i]\prod_{i=1}^N(1+(k_iv+b_i)x)\)，这是一个不超过 \(i\) 次的多项式。

如果每次朴素计算 \(g_{0\cdots N}\)，时间复杂度为 \(O(N^4)\)。

考虑到每次移动一次区间，只有 \(O(1)\) 个 \(k_iv+b_i\) 会发生改变，因此我们只需要做一次背包删除和背包插入。这样时间复杂度就是 \(O(N^3)\) 了。

ABC301Ex

简单题。考虑先建一个最小生成树出来。

如果修改的边 \((u,v)\) 不在树上，显然对答案没有影响。
如果修改的边 \((u,v)\) 在树上，考虑新的最小生成树，发现应当选取一端点在 \(u\) 这边，一端点在 \(v\) 这边的所有边中边权最小的边。可以转 DFS 序后二维数点，但复杂度至少为 \(O(N\log^2N)\)；对每条非树边在 \(u,v\) 处分别修改，然后线段树合并即可。这样时间复杂度为 \(O(N\log N)\)。

所以其实可以任意修改边权的。。

P3513

求将一个图 \(G=(V,E)\) 划分为一个独立集 \(S\) 和一个团 \(T\) 的方案数。

考虑两种划分 \((S_1,T_1),(S_2,T_2)\)，注意到：

至多存在一个 \(x\in S_1\)，使得 \(x\not\in S_2\)。

这是因为如果有两个 \(x,y\in S_1\)，那么必有 \((x,y)\not\in E\)。但另一方面，由 \(x,y\not\in S_2\Rightarrow x,y\in T_2\)，因此必须要有 \((x,y)\in E\)。这是矛盾的。

这样一来，一旦我们求出了一组合法解 \((S,T)\)，那么所有的合法解一定可以通过以下三种步骤得出：

从 \(S\) 中删掉一个点放进 \(T\) 中。
从 \(T\) 中删掉一个点放进 \(S\) 中。
从 \(S\) 中删一个点 \(x\) 放进 \(T\)，再从 \(T\) 中删一个点 \(y\) 放进 \(S\)。并且进一步地，如果存在这样的方案 \((S-x+y,T+x-y)\)，那么所有的方案一定形如 \((S-x+z,T+x-z)\) 或者 \((S-z+y,Y+z-y)\)。

这样一来，总共的方案数只有 \(O(n)\) 种。我们完全可以枚举每一种方案并一一判断，做到 \(O(n^2)\)；也可以通过维护加点与删点时两侧边数的变化来做到 \(O(n+m)\)。

最后说一下怎么获得一组合法解。比较简单的方法是采用 2-SAT：对每个点 \(i\)，我们设 \(p_i\in\{0,1\}\) 表示 \(i\) 是否在独立集内，那么只需对每个 \((i,j)\in E\) 连边 \(p_i=0\Rightarrow p_j=1\)，以及对每个 \((i,j)\not\in E\) 连边 \(p_i=1\Rightarrow p_j=0\) 即可。直接连边需要 \(O(n^2)\) 条边，不过我们可以用线段树优化建图，做到 \(O(n+m\log n)\)。这样总的时间复杂度就是 \(O(n+m\log n)\)。

UOJ449

首先有一个 minmax 容斥的做法：注意到如果要算一个 \(|T|=i\) 的 \(\mathbb E[\min_{i\in T}t_i]\)，那么最多 \(i\times k\) 次就会结束，因此可以做一个简单 DP 算出期望。具体来说，\(\text{Pr}[X>v]\) 就是将 \(v\) 粒玉米分配到 \(n\) 只鸽子头上，且每只鸽子只能分 \(<k\) 个。设 \(\text{dp}(i,j)\) 表示前 \(i\) 个分 \(j\) 粒玉米即可，复杂度 \(O(n^3k)\)，NTT 优化可以做到 \(O(n^2k\log(nk))\)。貌似 \(O(n^3k)\) 卡卡常也能过？

但说实话，你注意到本题的模型类似「每只鸽子都得超过 \(k\) 个」，min-max 容斥之后变成「每只都不许超过 \(k\) 个」，但本来较好算的就是前者。。~~因此我们容斥反倒把本题变难了orz~~

摁推！！不会推，摆了。

ABC302Ex

简单题。考虑一组询问咋做，把所有 \((A_i,B_i)\) 连边建图，显然答案是点数减去是树的连通块个数。

如何维护形态为树的连通块个数？可以用并查集维护，对每个连通块额外维护连通块内边数即可。

树上咋做？dfs 一遍，用可撤销并查集维护即可。\(O(N\log N)\)。

带撤销并查集写了个路径压缩，调了一年

ABC302G

简单题。考虑算出 \(1,2,3,4\) 各自的个数，然后把序列分成四段。设 \(a_{i,j}\) 表示在第 \(i\) 段中 \(=j\) 的元素个数，其中 \(1\le i,j\le 4\)。我们的目标是让所有 \(i\neq j\) 的 \(a_{i,j}\) 都变成 \(0\)。

显然，同一段内的操作是没用的。每次操作如果交换了两个数 \(x,y\)，他们分别在 \(i,j\) 这两段里，那么对 \(a\) 的影响就是：

\(a_{i,x}\leftarrow a_{i,x}-1,a_{i,y}\leftarrow a_{i,y}+1\)
\(a_{j,x}\leftarrow a_{j,x}+1,a_{j,y}\leftarrow a_{j,y}-1\)

然后对每行依次考虑，发现最优策略一定是先把形如 \((i,j)\) 和 \((j,i)\) 这样的位置消成 \((i,i),(j,j)\)，然后剩下的再匹配。由于 \(A_i\le 4\)，就算是第一行在匹配的时候也必然会在某一侧只留下一个非零元素，因此匹配方案是唯一的，可以保证最优。

LOJ2292

~~两年前 qbxt 就讲过的题怎么现在才来写啊~~

每次都抽取连续的一段，考虑区间 DP，\(f(l,r)\) 表示删空 \([l,r]\) 的最小 \(a\times k+\sum (\max_i-\min_i)^2\)。

考虑咋转移，发现最后一次删除可能是原区间的一个子序列，因此可以设 \(g(l,r,x,y)\) 表示将 \([l,r]\) 删到只剩值在 \([x,y]\) 中的数至少需要多少代价。那么有转移

\[g(l,r,x,y)=\begin{cases}g(l,r-1,x,y)&,w_r\in[x,y]\\\min_{l\le i<r}g(l,i,x,y)+f(i+1,r)&,w_r\not\in[x,y]\end{cases}\\ f(l,r)=\min_{x,y}g(l,r,x,y)+b\times (y-x)^2+k \]

离散化一手，时间复杂度就是 \(O(n^5)\)。

ABC301F

\(f(i,j)\) 表示前 \(i\) 个字符，恰好和 DDoS 类字符匹配上了前 \(j\) 个，没匹配上 \(j+1\) 的方案数。

转移就随便做一下，对于 \(f(i,1)\) 还需要多记录一下第一个 D 目前已经攒了多少种。看上去为了处理不是 ? 的位置我们需要状压一手，但实际上只需要记录一下当前非 ? 的位置已经出现了多少哪些元素，在遇到一个新的字符 \(c\) 时，若 \(c\) 确定出现过，那么一定是 \(f(i,1,x)\rightarrow f(i+1,2,x)\)；否则设非确定的位置已经攒了 \(x\) 种，\(c\) 不确定是否出现过，前面确定出现了 \(y\) 种，那么就是实际上可以把 \(f(i,1,x)\) 分成 \(\binom{26-y}{x-y}\) 种，其中每一种的方案数都相等。这其中有 \(\binom{26-y-1}{x-y}\) 种接不上，而

\[\frac{\binom{26-y-1}{x-y}}{\binom{26-y}{x-y}}=\frac{26-x}{26-y} \]

于是有 \(f(i,1,x)\times\frac{26-x}{26-y}\rightarrow f(i+1,1,x+1),f(i,1,x)\times\frac{x-y}{26-y}\rightarrow f(i+1,2)\)。

时间复杂度 \(O(n|\Sigma|)\)。

CF587D

感觉这题远远不到 *3100 啊

考虑一种颜色咋做，发现首先要满足每个点的度数不超过 \(2\)。这样一来，每个连通块就只可能是环或者链。进一步地，每个环都必须是偶环。不难发现，这也是充要条件。

这样一来，每个连通块必然是「选」与「不选」的边交替出现，因此只有两种方案。

对于多种颜色的情况，我们对每种颜色找出所有连通块，设所有颜色一共有 \(k\) 个连通块，我们的变量 \(x_1,x_2,\cdots,x_k\in\{0,1\}\) 就代表第 \(i\) 个连通块选哪种方案。对于两种异色连通块，他们之间可能有若干交点，这意味着某个 \(x_i=a\Rightarrow x_j=b\)。发现转化为 2-SAT 模型，可以在 \(O(n+m)\) 时间内求解。

对于原题，只需要二分答案一次，发现相当于钦定了某些 \(x_i\) 的取值，仍然只需要做 2-SAT。

时间复杂度为 \(O((n+m)\log V)\)。

QOJ5020

设 \(f_{x,d}\) 表示 \(x\) 子树内与 \(x\) 距离 \(\le d\) 的点数，\(g_{x,d}\) 表示 \(x\) 的轻儿子的所有子树内与 \(x\) 距离 \(\le d\) 的点数。

不妨先来考虑 \(y\) 是 \(x\) 祖先的情况，考虑如何算出此时 \(y\) 子树内有多少个点与这条链距离 \(\le d\)。发现这其实就是链上的点数，加上，链上每个点 \(u\) 的其他儿子的子树内，与 \(u\) 距离 \(\le d\) 的点数，之和。

考虑这条链 \(y\to x\)，发现链上的大部分边都是重边，只有 \(O(\log n)\) 条轻边。这也就意味着，如果我们要计算与这条链距离 \(\le d\) 的点数，对于大部分点，都只需要计算他们轻儿子内的信息；只有 \(O(\log n)\) 个点需要特殊处理重儿子的信息。具体来说，设这些轻边分别是 \((u_1,v_1),\cdots,(u_k,v_k)\)，其中 \(v_i\) 为 \(u_i\) 的父亲，那么答案就应该是链上所有点的 \(g_{\cdot,d}\) 之和，减去 \(\sum f_{u_i,d}\)，再加上 \(\sum f_{\text{hson}(v_i),d}\)。

考虑到 \(f\) 那部分一共只有 \(O(\log n)\) 项，而在 \(O(\log n)\) 时间内计算单点的 \(f\) 自然是简单的，于是这部分容易做到 \(O(n\log^2n)\)。现在考虑如何计算一条链上所有点的 \(g_{\cdot,d}\) 之和。

考虑差分成 \(1\to x\) 链上所有点的 \(g_{\cdot,d}\) 之和，我们注意到每个点的所有轻儿子的子树大小之和为 \(O(n\log n)\)，这允许我们从根开始往下 DFS，每次遇到一个点，就遍历他的所有轻儿子的子树内的所有点，并计算他对 \(g\) 的贡献。具体来说，我们动态地维护序列 \(G_i=\sum_{u\in\text{path}(1,x)}g_{u,i}\)，每次新进入一个点 \(x\) 时，暴力扫他的轻儿子的子树内的每个点 \(v\)，并令 \(G_{\text{dis}(v,x)}\leftarrow G_{\text{dis}(v,x)}+1\)。则查询只需查询前缀和，使用树状数组维护即可，时间复杂度 \(O(n\log^2n)\)。

最后，由于实际距离 \(\le d\) 的点可能在子树外，我们还需要使用某些树分治算法进行一遍树上邻域数点。这部分也容易做到 \(O(n\log^2n)\) 以内。

最后的最后，我们实际上询问的并非祖先-后代链：设实际询问的是 \(x\to y\) 这条链，\(z=\text{LCA}(x,y)\)，我们分别对 \(z\to x,z\to y\) 算出 \(z\) 子树内与这条链距离 \(\le d\) 的点数，那么多算的部分恰好就是 \(z\) 子树内与 \(z\) 距离 \(\le d\) 的点数，即 \(f_{z,d}\)。最后加上 \(z\) 子树外与 \(z\) 距离 \(\le d\) 的点数即可。

127 指出本题可以使用科技做到 \(O(n\log n)\)，并把这题搬到了模拟赛。

ABC220H

实在是听不懂 127 的 \(O(N^3/w)\) 做法，但是 \(O(N\times 2^{\frac{N}{2}})\) 做法还是挺简单的！

首先转成补图，变成取一个导出子图，那么现在要求点集内边的奇偶性和 \(M\) 一致。

把 \(N\) 个点平均分成两部分，分别求出 \(f(S),g(T)\) 表示左侧的 \(S\) 点集与右侧点集 \(T\) 内边数奇偶性。

现在考虑拼接两个集合 \(S,T\)，发现会有若干跨过去的边。枚举左侧集合 \(S\)，设 \(S\) 延伸到右侧的若干边的另一端点构成集合为 \(T_0\)，那么相当于要在右侧选出一个 \(T\)，这个点集 \(S\cup T\) 的导出子图内的边数奇偶性就是 \(f(S)\text{ xor }g(T)\text{ xor }x\)，其中 \(x\) 为 \(S\) 延伸过去的边数的奇偶性。

我们仔细想一下这个延伸过去的边数到底是啥，发现只有 \(T_0\) 中与 \(S\) 中连边个数为奇数的点能造成贡献。设 \(c(S)\) 表示所有满足 \(x\) 到 \(S\) 中连边个数为奇数的点构成的集合，那么跨越两端的边数的奇偶性就是 \(\text{popcount}(c(S)\text{ and }T)\) 的奇偶性。

看着就很像 FWT 对吧！套路地把这个奇偶性变为 \(\frac{1}{2}(1+(-1)^{\text{popcount}(c(S)\text{ and }T)})\)，然后就成功凑出了 FWT 的形式。具体来说，我们按照 \(f,g\) 的奇偶性分成四类，以 \(f(S)=0\) 的 \(S\) 为例，首先求出 \(h(S)\) 表示满足 \(c(S_0)=S\) 的 \(S_0\) 个数，那么对于右侧的 \(T\)，根据 \(g(T)\) 的值就可以知道我们想要的 \(\text{popcount}(c(S)\text{ and }T)\) 的奇偶性。

如果想要 \(\text{popcount}(c(S)\text{ and }T)\) 为偶数，那么左侧能和 \(T\) 拼上的 \(S\) 的数目就是

\[\begin{aligned}\text{ans}(T)&=\sum_{f(S)=0}\frac{1+(-1)^{\text{popcount}(c(S)\text{ and }T)}}{2}\\&=\frac{1}{2}\left(\sum_{f(S)=0}1+\sum_{S}h(S)(-1)^{\text{popcount}(S\text{ and }T)}\right)=\dfrac{1}{2}\left(\text{FWT}(h)[T]+\sum_{f(S)=0}1\right)\end{aligned} \]

发现只需要给 \(h\) 做一个 FWT 就可以了。总的时间复杂度为 \(O(N2^{N/2})\)。

QOJ4549

\(f(u)\) 表示 \(u\) 子树的 SG 值，那么转移相当于选一个 \(v\)，删掉这条链后必然会形成若干子树，该后继的 SG 值就是这些子树的 SG 值的 xor 和。最后还需要对这些东西取 mex。

考虑所有这些后继状态，发现如果我们设 \(S(u)\) 表示 \(u\) 子树的所有后继状态的 SG 值构成的集合，实际上对于一个点 \(u\)，设其儿子分别为 \(v_1,\cdots,v_k\)，那么他的 \(S(u)\) 就是：将每个 \(S(v_i)\) 异或上所有 \(j\neq i\) 的 \(f(v_j)\)，然后再取并集，再插入所有 \(f(v_i)\) 的异或（表示第一次操作删除了 \(u\) 自己）。

那么我们就是要用数据结构维护一个集合，支持全局异或，插入，合并，查询全局 mex 这三种操作。

使用 01trie 维护即可，单组数据复杂度 \(O(n\log n)\)。

举办乘凉州喵，举办乘凉州谢谢喵 in 1log

上回书说到，我们把这题分成了三部分：计算 \(O(n\log n)\) 次某个 \(f_{u,d}\) 的值，计算 \(O(n)\) 次某条链上 \(g_{u,d}\) 的和，计算 \(O(n)\) 次与某个点距离 \(\le k\) 的点数。下面我们分别把这三部分优化至 \(O(n\log n)\)。

\(O(1)\) 计算 \(f_{u,d}\)：设 \(\text{size}(u)\) 表示点 \(u\) 的子树大小，那么 \(f_{u,d}\) 其实就是 \(\text{size}(u)\) 减去所有 \(u\) 的 \(d+1\) 级儿子的子树大小之和。于是我们只需要计算某一 DFS 序区间内深度 \(=d+1\) 的点的 \(\text{size}\) 之和，可以简单用前缀和做到均摊 \(O(1)\)。
\(O(1)\) 维护 \(G_d=\sum_{u\in\text{path}(1,x)} g_{u,d}\)：同理，只需要维护单点加单点求值，开桶维护即可。
\(O(n\log n)\) 进行邻域数点：点分治后维护前缀和即可。

综上，本题在 \(O(n\log n)\) 的时间复杂度内得到解决。代码待补

codeforces 2023.5 2023