ZR24NOIP1B. 数数

给你一个长度为 \(n\le 1600\) 的二进制数，其中某些位未知，是 ?。问 ? 的所有取值得到的 \(x\)，\([0,x-1]\) 中不含长度为 \(k\le 20\) 的回文串的数字（含前导 \(0\)）的个数的和。

首先显然是数位 DP。

考虑从高位枚举到低位，假设没有 ?，状态记位数 \((1600)\) 和是否顶到上界 \((0/1)\)。枚举第 \(i\) 位填什么数字，需要判断填上之后会不会和前面 \(k-1\) 位形成一个回文串，因此我们还要记录前 \(k-1\) 位是什么 \((2^{19})\)。有问号的话转移的时候再枚举一下 ? 填什么就好了。然后判断回文串，但是显然这样过不了。我们直接预处理所有可能的回文串 \((2^{10})\)，然后把他们丢到 AC 自动机里，状态改记 AC 自动机节点编号，转移的时候跳一下指针。容易发现因为回文串左右两边是一样的，所以回文串个数只有 \(2^{10}\)。

复杂度：AC 自动机预处理时间和空间都是 \(2^{\frac{k}{2}}k\)，DP 转移状态是 \(n2^{\frac{k}{2}}k\) 的，可以通过。