题解：P3781 [SDOI2017] 切树游戏

· · 题解

最近有时间来深入学习一下动态 DP，写一下题解。（进入博客观感更佳）

正文内容

直接开推 DP 式子：设 dp_{u,i} 表示以 u 为连通块最高点，异或值为 i 的方案数。

这里的 dp'_{u,i} 表示在加入 v 子树前的 dp 数组。

dp_{u,i}=dp'_{u,i}+\sum_{j \oplus k=i} dp'_{u,j} \times dp_{v,k} \\dp_{u,a_u}=1

然后我们发现右边是一个 FWT 的形式。

注：以下解读只是本人作为一个初学 FWT 的一个认识，可能会有不对的地方，如果有误，请在评论区提出，谢谢。

我们知道把 dp'_u 和 dp_v FWT 后按位相乘后进行一次 IFWT，可以对于每一位得到上述式子右边的部分，但是其实 FWT/IFWT 有一个非常良好的性质，其为线性变换，具体就是：

定义一般大写字母表示数组，小写字母表示一个数，数组 +/\times 另一个数组表示两个数组按位相加/相称，数 \times 数组表示数组中的每个数乘以这个数。

FWT[A+C]=FWT[A]+FWT[C] \\FWT[c\times A]=c \times FWT[A]

所以我们对等式两边做 FWT 实际上是等价的，原因如下：

我们把原式变化一下（下面为了方便，把 ' 给去掉了）:

dp_{u,i}=dp_{u,i}+\sum_{j \oplus k=i} dp_{u,j} \times dp_{v,k} \\= \\dp_{u,i}=dp_{u,i}+IFWT[FWT[dp_u]\times FWT[dp_v]]_i

这个就是 FWT 的基本方法了，看不懂这一步变形的可以回去在看一下 FWT 的操作。

\because FWT[A+C]=FWT[A]+FWT[C] \\\therefore FWT[dp_u]_i=FWT[dp_u]_i+FWT[IFWT[FWT[dp_u]\times FWT[dp_v]]]_i \\\therefore FWT[dp_u]_i=FWT[dp_u]_i+FWT[dp_u]_i\times FWT[dp_v]_i \\\therefore FWT[dp_u]_i=FWT[dp_u]_i\times(FWT[dp_v]_i+1)

倒数第二步变形是因为 FWT 和 IFWT 是互逆的运算，所以可以抵消。

这实际是告诉我们，我们在做 DP 的时候可以直接对 DP 数组 FWT 然后按上面的式子算，最后 IFWT 回来就行。

所以初始化为 FWT[a_u] 表示在只有 a_u 这位是 1，其他都是 0 的 FWT 结果。（实际上就是对正常 DP 的初始化进行 FWT）

那问题就来了，其他的计算也可以 FWT 后直接计算吗，那我们来看一下下面要进行的操作。（为了方便，下面的 DP 数组默认进行 FWT）

然后我们发现暴力计算和修改是 O(qnm\log m) 的。

然后修改很容易想到动态 DP，所以继续推式子：

最后询问 k 的答案是 \sum IFWT[dp_{u}]_i，所以我们要对其求和，设 g_{u,i} 表示在 u 子树中的所有点 x 的 dp_{x,i}（这里不是 FWT 后的）的和。

g_{u,i}=\sum g_{v,i} + dp_{u,i}

然后这个式子只是加法运算，所以两边同时 FWT 也是不变的，那这个 g 数组也可以先 FWT 在计算最后变回来。（所以下面的 g 也是默认 FWT 后的结果）

结合动态 DP 的思想，设 son_u 表示 u 的重儿子，dpl_{u,i}=\prod_{v \ne son_u} (dp_{v,i}+1)，gl_{u,i}=\sum_{v \ne son_u} g_{v,i}

dp_{u,i}=FWT[a_u]_i\times dpl_{u,i} \times (dp_{son_u,i}+1) \\g_{u,i}=gl_{u,i}+g_{son_u,i}+dp_{u,i}

然后就是喜闻乐见的矩阵转移：

\begin{bmatrix} dpl_{u,i}\times FWT[a_u]_i & 0 & dpl_{u,i}\times FWT[a_u]_i \\ dpl_{u,i}\times FWT[a_u]_i & 1 & dpl_{u,i}\times FWT[a_u]_i+gl_{u,i} \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} dp_{son_u,i} \\ g_{son_u,i} \\ 1 \end{bmatrix}= \begin{bmatrix} dp_{u,i} \\ g_{u,i} \\ 1 \end{bmatrix}

然后全局平衡二叉树修改 gl 和 dpl 数组即可。（不用会超时！

~然后就结束了。~

开玩笑的，我们知道了动态 DP 的修改只涉及 +/\times（-/\div 可以用 +/\times 代替），所以我们就可以放心的把所有数组 FWT 后，最后 IFWT 即可。

但是这个题有一些坑和一些有趣的 trick：

  1. 本题目的时间复杂度是 O(qm\log n) 的，所以其实卡的比较死，那你矩阵乘法自带的 3\times 3 的常数就太大，但是还有一种方法，手玩一下：
\begin{bmatrix} a1 & 0 & b1\\ c1 & 1 & d1\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a2 & 0 & b2\\ c2 & 1 & d2\\ 0 & 0 & 1 \end{bmatrix}= \begin{bmatrix} a1a2 & 0 & a1b2+b1\\ c1a2+c2 & 1 & c1b2+d2+d1\\ 0 & 0 & 1 \end{bmatrix}

所以实际上只用做 4 次加乘即可。（但是我发现循环展开好像比这个做法快？算了，还是建议学一下）

  1. 本题中的 dpl 数组会是要修改的，有可能会除以 0，所以可以开一个结构体，把一个数表示成 x\times 0^y 的形式，除 0 的时候把 y 减少即可。

然后应该就没有然后了。

不喜勿喷。

code