Luogu6811 「MCOI-02」Build Battle 建筑大师

题意：给出 ，有 次询问。

每次询问给出 ，求长为 的 的循环串的本质不同子序列数。

答案对 取模，，时限 。

---

先对一个 单独求解。

对原来的文本串，建立子序列自动机，然后求自动机上的路径条数即可。

由于本题中的文本串是循环串，节点 到节点 各有一条边。

这样，设 是从节点 出发的路径条数（包括空），转移方程如下 ：

最后的答案是 。

为了方便，把 翻转一下。则有 答案是 。

有个 很不爽，想办法消掉。

注意到 即有

---

考虑如何优化这个递推。编个组合意义试试看。

从 号点出发，初始权值为 ，若向前走一步，权值 ，若向前走 步 ,权值 。

对所有到达 的方案的权值求和，即为答案。

显然，最终的权值只和两种移动方式的使用次数有关。

枚举走 步的次数 ，那么走 步的次数就是 。故答案是

对于每个 暴力计算，复杂度为 。