CF177G1/CF177G2 Fibonacci Strings 题解

zrl123456 · 2025-10-06 23:21:30 · 题解

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

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

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

f_1=\texttt{a}
f_2=\texttt{b}

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

G1：
- 1\le n,q,\displaystyle\sum|p|\le 3000
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

CF177G1/CF177G2 Fibonacci Strings 题解

G2：