【题解】P8885 dp套dp 矩阵乘法优化dp 分治
ღꦿ࿐
·
·
题解
感觉全是套路的一个题，但很有意思，适合当 dp 套 dp 思想的入门理解。模拟赛赛时搬了个卡常版本被卡成了 60，很神笔，感觉这题难度不在数据结构部分吧。
定义一个串是奇的当且仅当这个串有奇数个本质不同可空子序列。
定义一个串是好当当且仅当这个串有奇数个奇子串。
\text{Part 1} 本质不同子序列计数（奇串的判定）
广为人知。
考虑求出一个固定位置
维护 f_{i,c} 表示前 i 个位置，目前以 c 结尾的子序列计数。
转移方式：
f_{i,a_i}=\sum f_{i-1,j}+1
f_{i,j}=f_{i - 1,j} (j\neq a_i)
即对于所有原本的子序列（包含空串），新加入一个数都可以使得它变成一个以这个数结尾的子序列，而对于其他串，并不以它结尾的子序列的个数。
把 f 数组拍平（滚动数组）。我们只需要记录每个位置的奇偶性。
考虑和为 0 的时候会将 f_{a_i} 赋值为 1，而此时和为 1 的时候会将 f_{a_i} 赋值为 0，所以 f 数组中无论如何是只会有不超过 1 个 1 的，考虑记录一个 f_{U}，表示 f_{0}+f_{1}+1，即该串的本质不同子序列数，那么在数组后面放一个 a_i，相当于交换 f_{U} 和 f_{a_i} 的奇值，过程如下。
f'_{a_i} = \sum f_{j} = f_U
f'_{U} = f_{U} + f'_{a_i} - f_{a_i}=2f_U-f_{a_i}=f_{a_i}
所以我们只需要记录目前哪个位置的 f 有值即可递推信息并维护本质不同子序列数。
\text{Part 2} 奇子串计数（好串的判定）
因为 f dp 统计的是一个串的 dp 数，现在统计的就是所有子串的 f 数组的信息，又因为我们要一位一位来，所以
考虑 dp 套 dp：统计目前 f 数组的 dp 值对应的子串数。
令 g_{of} 表示目前这个串的 f dp数组为 of 的子串个数，其中 of 被简化为 \{0,1,U\} 表示有值位置。
统计所有子串的方式即是：对于每个位置：
- 加入一个以这个位置开头的空串。
- 进行转移—— 原本的 f 添加了末尾的数会转移到 f'，那么就将 g_{f} 转移到 g_{f'}。
- 统计所有以此位置结尾的奇串个数，累加至 tot 中。
因为 f 只有 3 个有意义的值，所以 g_{f} 存三个状态。
我们可以统计对整个子串进行上面这个过程，通过 tot 的奇偶性来判断这个串是否为好串。
\text{Part 3} 填充方案数计数（将好串的判定放入计数中）
我们已经能够统计这个子串是否是好的，只需要维护 g_{0/1/U} 和 tot 的值，接下来我们要维护所有填充方案的好串的判定。
考虑再套一层 dp：统计目前 g 数组与 tot 对应的的填充方案。 h_{ (g,tot)} 表示目前填充方案使得目前的共统计状态为 g 和 tot，因为本质不同的 g_{f} 与 tot 只有 2^4 种，所以 h 的状态只有 16 种。
在确定了这个状态后某个 (g,tot) 会转移至 (g',tot') 那么在进行转移时将 h_{(g,tot)} 转移至 h'_{(g',tot')} 即可。
直接进行转移，时间复杂度 O(q n \times s)，其中 s=16。
\text{Part 4} 数据结构优化
观察到这个区间查询的 dp 的形式是一个线性的转移，且第二维较小，考虑使用矩阵乘法优化转移，使用数据结构区间查询某段矩阵的乘积，时间复杂度可以做到 O( (n+q\log n)s^3)，很基础不在赘述。
\text{Part 5} 常数优化与状态减少
首先线段树查询不需要整个矩阵的信息，故将矩阵乘矩阵优化成向量乘矩阵，复杂度 O(ns^3+qs^2\log n)，可以过掉这个题了。
首先这个矩阵的大小是很大的，但是单个位置的转移矩阵较为稀疏只有 O(s) 个值，这样的矩阵的乘法是可以 O(s^2) 完成的，所以我们不想像线段树那样合并两个一般矩阵，考虑猫树分治求答案，这样维护前后缀乘积的答案就是一般矩阵乘上单个转移矩阵，复杂度 O(n \log n s^2 + qs^2)。
在复杂度上我们很难再优化了，但是状态数还可以再减少！观察到我们前面处理 g 的时候加入的串的总数的奇偶性是固定的（给 g_{U} 改变了一次奇偶性，所以我们是可以通过目前的总长度和 g_0,g_1 推出来 g_{U}，故可以将需要记录的的状态减少 3 个，可以将 s 减小到 8，但是需要分别记录奇数和偶数的矩阵，将一个常数 2 从平方内移到了平方外，会快很多。
笔者没加最后这个优化，目前最优解第二，这里是代码。