本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-06 23:21:30

:::::info[闲话] 已完成今日模拟赛挂分 180pts 大学习。
::::: :::::info[题目基本信息] 考察：

• G1：KMP 算法（$2400$）。
• G2：KMP 算法，矩阵加速（$2600$）。

题目简介：
定义斐波那契串为：

• $f_1=\texttt{a}$
• $f_2=\texttt{b}$
• $\forall i\ge 3,f_i=f_{i-1}+f_{i-2}$，其中 $+$ 表示字符串拼接。

给定 $n$，$q$ 次询问，每次给出一个字符串 $p$，求 $p$ 在 $f_n$ 里的出现次数（对 $10^9+7$ 取模）。
数据范围：

1. G1：

• $1\le n,q,\displaystyle\sum|p|\le 3000$

2. G2：

• $1\le n\le 10^{18}$
• $1\le q\le 10^4$
• $1\le\sum|p|\le 10^5$ ::::: G1 对 G2 几乎毫无启发，我们直接看 G2（绝对不是因为不会，而是因为这是 G2 题解）。

G2：

首先在 $n\le 10^{18}$ 时 $|f_n|$ 是很爆炸的，我们不能直接算。
在放弃数据结构等若干方法后，我们考虑 DP，设 $F_n$ 为 $f_n$ 中 $p$ 的出现次数，容易发现出现的 $p$ 只能有这三种情况：

• 出现在 $f_{n-1}$ 中。
• 出现在 $f_{n-2}$ 中。
• 一段非空前缀出现在 $f_{n-1}$ 中，一段非空后缀出现在 $f_{n-2}$ 中。

设第 $3$ 种情况的出现次数为 $F'n$，那么我们得到：
$$F_n=F{n-1}+F_{n-2}+F'n$$ 现在我们重点解决 $F'_n$。
想要既有字符出现在 $f{n-1}$ 中，又有字符出现在 $f_{n-2}$ 中，那么它一定出现在 $f_{n-1}$ 的后 $|p|$ 个字符和 $f_{n-2}$ 的前 $|p|$ 个字符拼接形成的字符串中，长度大约是 $2\times 10^5$，看起来没有那么爆炸了，但是还是不能直接做。
但是我们观察得到，$f_{n-1}$ 的后 $|p|$ 个字符和 $f_{n-2}$ 的前 $|p|$ 个字符拼接形成的字符串经过一定时间就没有几种情况了，因为根据原式 $f_i=f_{i-1}+f_{i-2}$，$f_i$ 的前 $|p|$ 个字符在字符串足够长的时候与 $f_{i-2}$ 的相同，后 $|p|$ 个字符同理，考虑找出这个位置。
由于首先这个字符串要有 $|p|$ 个字符，所以我们先找到第一个使得 $|f_{pos}|\ge|p|$ 的 $pos$，这个直接暴力预处理暴力跑就行，简单分析一下发现每次询问会有 $\Theta(\log |p|)$ 的复杂度，跟没有一样。预处理的时间复杂度简单分析一下发现下界是 $\Theta(|p|\log |p|)$ 的，也不大。
我们找到了 $pos$，不断尝试 $pos,pos+1,pos+2,\dots$，最终我们发现这个拼接而成的字符串会在 $pos+4$ 以后就不变了，那么当 $n\le pos+3$ 时我们就可以直接跑 KMP 算答案，此时字符串长度上界也才 $8|p|$，稳稳的。
那么我们现在要算 $n\ge pos+4$ 时的答案，此时容易得到 $F'n=F'{n-2}$，我们进行推导：
$$F_{n-2}=F_{n-3}+F_{n-4}+F'{n-2},F'{n-2}=F'n\\Leftrightarrow F'_n=F{n-2}-F_{n-3}-F_{n-4}$$ 代入 $F_n=F_{n-1}+F_{n-2}+F'n$ 得： $$F_n=F{n-1}+2F_{n-2}-F_{n-3}-F_{n-4}$$ 这个东西显然可以用矩阵快速幂维护，开一个 $siz=4$ 的矩阵即可。
然后做完了，代码长度也并不长，感觉就是 KMP 板子和矩阵快速幂板子拼了起来。
时间复杂度为 $\Theta(\max|p|\log\max|p|+\sum|p|+qsiz^3\log n)$，空间复杂度为 $\Theta(siz^3+\sum|p|)$。

code