斐波那契串的后缀恒定、前缀只与下标奇偶有关,于是跨界匹配数按奇偶取两个定值,先暴力打出前几项再用 3x3 矩阵快速幂推到第 N 项。
OJ: roj
题目 ID: 1796
难度:提高+/省选-
标签:数学字符串矩阵快速幂KMPpython
创建: 2026-10-08 03:44
更新: 2026-10-08 03:44
形式化题目
定义
其中
约束为 0、1。
关于题面笔误。 题面把初值写成 "0",则所有 problem8(
正解
思路
朴素做法与它的瓶颈。 最直接的想法是按定义把
问题在于长度按斐波那契增长:int 上界,
观察一:答案可以递推。 因为
观察二:跨界项只看两端的短片段。 若一个匹配跨越了拼接缝,它的起点必落在左块末尾
观察三:这两个短片段是周期的。 取最小的
- 因为
永远以 结尾, 一路传下去,后缀是一个常量; - 因为
永远以 开头, , 前缀只与下标的奇偶有关,奇偶各有一个常量。
两者相乘,就得到本题最值钱的结论:从某个下标起,
用
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 3 | 4 | 8 | 12 | 21 | 33 | 55 | |
| — | — | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
0,1,0,1,… 交替,
观察四:把它变成常系数递推。 取一个足够大的偶数下标
因为
其中
实现细节一:两个常量由容斥反推,不手推前后缀。 直接把
这正是把递推式移项后的结果,比手写前后缀匹配短得多,也不容易错。
实现细节二:临界值不能取小。 前缀“按奇偶稳定”需要
实现细节三:矩阵快速幂。 把
对指数
小 problem8 就是
代码
Python 版(functools 都没用上,全部按表达式写):
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:45
# update_at: 2026-10-08 03:45
import sys
# 斐波那契串 S[i] 的跨界贡献 cross[i] 从 i >= K+3 起只随 i 的奇偶取两个定值,
# 所以递推按"步长 2"做,状态是列向量 (f[e+2k], f[e+2k+1], 1)^T。
STEP = 2 # 递推步长 = cross 的周期
NEED_AHEAD = 5 # 在 K 之外多构造几项,够容斥反推两个常数即可
# 类型别名(Python 3.12+ 的 type 语句):3x3 转移矩阵,行优先
type Matrix = list[list[int]]
def prefix_function(t: str) -> list[int]:
"""t 的前缀函数(失配数组),pi[i] = t[0..i] 的最长真前后缀长度。"""
pi = [0] * len(t)
for i in range(1, len(t)):
j = pi[i - 1]
while j and t[i] != t[j]:
j = pi[j - 1]
if t[i] == t[j]:
j += 1
pi[i] = j
return pi
def count_occ(s: str, t: str, pi: list[int], m: int) -> int:
"""t 在 s 中作为子串的出现次数(允许重叠),O(|s|)。"""
if len(s) < m:
return 0
cnt = j = 0
for ch in s:
while j and ch != t[j]:
j = pi[j - 1]
if ch == t[j]:
j += 1
if j == m:
cnt += 1
j = pi[j - 1]
return cnt
def mat_mul(x: Matrix, y: Matrix, mod: int) -> Matrix:
"""3x3 矩阵乘法后取模。"""
r = [[0] * 3 for _ in range(3)]
for i in range(3):
for k in range(3):
xa = x[i][k]
if not xa:
continue
for j in range(3):
r[i][j] = (r[i][j] + xa * y[k][j]) % mod
return r
def mat_pow(b: Matrix, e: int, mod: int) -> Matrix:
"""3x3 矩阵快速幂,O(log e) 次矩阵乘法。"""
r = [[int(i == j) for j in range(3)] for i in range(3)]
while e:
if e & 1:
r = mat_mul(r, b, mod)
b = mat_mul(b, b, mod)
e >>= 1
return r
def fib_count(n: int, m: int, p: int, t: str) -> int:
"""T 在 S[n] 中的出现次数模 p:小 n 暴力打表,大 n 走矩阵快速幂。"""
pi = prefix_function(t)
# 题面把 S[1] 写成 "0" 是笔误(那样全串皆 0),按样例与真实数据应为 S[0]="0", S[1]="1"
seq = ["0", "1"]
while len(seq[-1]) < m - 1:
seq.append(seq[-2] + seq[-1])
# K = 最小的下标使 |S[K]| >= M-1;从 K 起前后缀长度足够,跨界形态才稳定
k = next(i for i, si in enumerate(seq) if len(si) >= m - 1)
need = min(n, k + NEED_AHEAD) # 小 N 时得把 S[n] 也拼出来
while len(seq) - 1 < need:
seq.append(seq[-2] + seq[-1])
f = [count_occ(si, t, pi, m) for si in seq] # f[i] = T 在 S[i] 中的精确次数(不取模)
if n <= need: # 已经能直接回答,不进矩阵
return f[n] % p
e = k + 3 if (k + 3) % STEP == 0 else k + 4 # 第一个 >= K+3 的偶下标
a0, b0 = f[e], f[e + 1]
c_even = f[e] - f[e - 1] - f[e - 2] # 偶数步的跨界次数 cross[e]
c_odd = f[e + 1] - f[e] - f[e - 1] # 奇数步的跨界次数 cross[e+1]
# a' = a + b + c_even, b' = a + 2b + c_even + c_odd,第三列 1 承载常数项
base = [[1, 1, c_even], [1, 2, c_even + c_odd], [0, 0, 1]]
r = mat_pow(base, (n - e) // STEP, p)
va = (r[0][0] * a0 + r[0][1] * b0 + r[0][2]) % p # f[n],n 与 e 同奇偶
vb = (r[1][0] * a0 + r[1][1] * b0 + r[1][2]) % p # f[n],n 与 e 奇偶不同
return va if (n - e) % STEP == 0 else vb
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m, p = next(data), next(data), next(data)
t = next(data).decode()
print(fib_count(int(n), int(m), int(p), t))
if __name__ == "__main__":
solve()C++ 版(同一算法,用 __int128 承接模数乘法):
// ROJ 1796《斐波那契串》
// ---------------------------------------------------------------------------
// 题意(题面见 problem.md):
// S[0]="0", S[1]=? , S[i]=S[i-2]+S[i-1](字符串拼接)。
// 给定 N,M,P 与长度 M 的 0/1 串 T,求 T 在 S[N] 中作为子串的出现次数(可重叠)mod P。
//
// 【题面笔误】content.md 写 “S[1]="0"”,但若 S[0]=S[1]="0" 则所有 S[i] 全为 0,
// 样例 T="101" 在 S[7] 中不可能出现 8 次(恒为 0),与样例输出 8 矛盾。
// 结合真实数据 problem8(N=10^9, M=1, T="1",答案非 0)可确认正确初值是
// S[0]="0", S[1]="1"(即经典 Fibonacci word)。本题按此建模。
//
// 【算法】O(M + log N)
// 记 f[i] = T 在 S[i] 中的出现次数。S[i]=S[i-2]S[i-1],故
// f[i] = f[i-2] + f[i-1] + cross[i],
// cross[i] 为“跨越拼接缝”的出现次数(起点落在左块 S[i-2] 内、终点落在右块 S[i-1] 内)。
// 跨界的匹配只可能向左伸入 M-1 个字符、向右伸入 M-1 个字符,因此 cross[i] 只由
// suffix_{M-1}(S[i-2]) 与 prefix_{M-1}(S[i-1]) 决定。
// 取最小的 K 使 |S[K]| >= M-1(M<=10^4 保证 K<=21):
// * S[i] 以 S[i-1] 结尾 => 对 i>=K+1,suffix_{M-1}(S[i]) 恒等于 suffix_{M-1}(S[K]),恒定;
// * S[i] 以 S[i-2] 开头 => 对 i>=K+2,prefix_{M-1}(S[i]) = prefix_{M-1}(S[i-2]),只与奇偶有关。
// 于是对 i>=K+3,cross[i] 只随 i 的奇偶取两个定值,即 cross[i]=cross[i+2]。
//
// 实现上不手推前后缀,直接暴力构造 S[0..min(N,K+5)] 并用 KMP 数出精确的 f[i],
// 再用容斥反推两个常数:cEven = f[e]-f[e-1]-f[e-2],cOdd = f[e+1]-f[e]-f[e-1](e 为 >=K+3 的偶数)。
// 之后按“步长 2”递推(a_k=f[e+2k],b_k=f[e+2k+1]):
// a_{k+1} = a_k + b_k + cEven
// b_{k+1} = a_k + 2*b_k + cEven + cOdd
// 写成 3x3 转移矩阵,对 (a,b,1) 做快速幂,指数 k=(N-e)/2,O(27 log N)。
//
// 【来源】本题素材源带 data.py 生成脚本,data/ 为自造数据;std.cpp 与本实现独立,
// 算法思路一致(均为“前后缀稳定 + 跨界计数 + 矩阵快速幂”)。正确性以 10 个真实点为准。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
static ll N, P; // N 为迭代次数,P 为模数
static int M; // 模式串长度
static string T; // 模式串
static vector<int> piArr; // T 的失配数组(前缀函数)
// 预处理 T 的前缀函数,O(M)
static void buildPi() {
piArr.assign(M, 0);
for (int i = 1; i < M; i++) {
int j = piArr[i - 1];
while (j > 0 && T[i] != T[j]) j = piArr[j - 1];
if (T[i] == T[j]) j++;
piArr[i] = j;
}
}
// 统计 T 在 s 中的出现次数(允许重叠),O(|s|)
static ll countOcc(const string &s) {
if ((ll)s.size() < (ll)M) return 0;
ll cnt = 0;
int j = 0;
for (int i = 0; i < (int)s.size(); i++) {
while (j > 0 && s[i] != T[j]) j = piArr[j - 1];
if (s[i] == T[j]) j++;
if (j == M) { cnt++; j = piArr[j - 1]; }
}
return cnt;
}
// 3x3 矩阵(mod P)
struct Mat {
ll a[3][3];
Mat() { memset(a, 0, sizeof(a)); }
};
static Mat mul(const Mat &x, const Mat &y) {
Mat r;
for (int i = 0; i < 3; i++)
for (int k = 0; k < 3; k++) {
if (!x.a[i][k]) continue;
for (int j = 0; j < 3; j++)
r.a[i][j] = (ll)((r.a[i][j] + (lll)x.a[i][k] * y.a[k][j]) % P);
}
return r;
}
static Mat matPow(Mat b, ll e) {
Mat r;
for (int i = 0; i < 3; i++) r.a[i][i] = 1 % P; // P=1 时单位元取 0,保持模意义一致
while (e > 0) {
if (e & 1) r = mul(r, b);
b = mul(b, b);
e >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> M >> P)) return 0;
cin >> T;
if ((int)T.size() != M) T.resize(M, '0'); // 容错:输入串长度应与 M 一致
buildPi();
// 求最小的 K 使 |S[K]| >= M-1(长度迅速超过 M-1 <= 9999,K <= 21)
vector<ll> len;
len.push_back(1); // S[0] = "0"
len.push_back(1); // S[1] = "1"
int K = 0;
for (int i = 0;; i++) {
if (i >= 2) len.push_back(len[i - 1] + len[i - 2]);
if (len[i] >= (ll)M - 1) { K = i; break; }
}
// 需要构造的串下标上界:min(N, K+5)(K+5 保证 a0,b0 与两个常数都可用)
ll need = min<ll>(N, (ll)K + 5);
vector<string> S;
S.push_back("0");
if (need >= 1) S.push_back("1");
while ((ll)S.size() - 1 < need) {
int c = (int)S.size() - 1;
S.push_back(S[c - 1] + S[c]);
}
// 暴力统计精确的 f[i](不取模,最大也才 |S[K+5]| ~ 2*10^5)
vector<ll> f(need + 1, 0);
for (ll i = 0; i <= need; i++) f[i] = countOcc(S[(int)i]);
if (N <= need) { // 小 N:直接输出
cout << (f[N] % P) << "\n";
return 0;
}
// 现在必有 N > K+5,长度足够,跨界计数已进入周期 2 的稳定区
ll e = ((K + 3) % 2 == 0) ? (ll)(K + 3) : (ll)(K + 4); // 第一个 >= K+3 的偶数下标
ll a0 = f[e], b0 = f[e + 1];
ll cEven = f[e] - f[e - 1] - f[e - 2]; // cross[e]
ll cOdd = f[e + 1] - f[e] - f[e - 1]; // cross[e+1]
Mat base;
base.a[0][0] = 1 % P; base.a[0][1] = 1 % P; base.a[0][2] = ((cEven % P) + P) % P;
base.a[1][0] = 1 % P; base.a[1][1] = 2 % P; base.a[1][2] = (((cEven + cOdd) % P) + P) % P;
base.a[2][2] = 1 % P;
ll steps = (N - e) / 2;
Mat R = matPow(base, steps);
ll va = (ll)(((lll)R.a[0][0] * (a0 % P) + (lll)R.a[0][1] * (b0 % P) + R.a[0][2]) % P);
ll vb = (ll)(((lll)R.a[1][0] * (a0 % P) + (lll)R.a[1][1] * (b0 % P) + R.a[1][2]) % P);
ll ans = ((N - e) % 2 == 0) ? va : vb;
ans = ((ans % P) + P) % P;
cout << ans << "\n";
return 0;
}复杂度
- 时间:构造串到
需要 ,其中 ( 的定义 决定了 是首个 的斐波那契长度, ); KMP 统计同样 ,因为只需对前常数个串各跑一次。矩阵快速幂是 。整体 , 、 时实测 10 ms (限时 1000 ms)。 - 空间:字符串存到
为止, ;矩阵与状态是常数级。实测峰值 8.3 MB(限时 256 MB)。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两种语言版本, 复杂度完全同阶。Python 侧省去了 C++ 里的__int128——Python 整数天然无溢出, 矩阵乘法直接乘再取模即可。
总结
- 递推的目标是“消灭下标依赖”。
本身 并不是常系数递推,因为 随 变;发现它周期为 2 之后, 两步一合并才拿到可以快速幂的常系数形式。 - 周期性的来源是“两端稳定”:斐波那契串永远以
结尾、以 开头, 于是长为 的后缀冻结成常量、前缀按奇偶分裂成两个常量。 这是本题从“无法构造的无穷串”跳到“有限状态”的桥梁。 - 跨界项不必手推前后缀:
是递推式移项的直接产物, 比显式 KMP 匹配前后缀更短、更不易错,也让 这类退化情形自动成立。 - 初值必须按样例修正:题面写
与样例输出 矛盾, 真实数据也否定了全零读法,故取 。读题时“样例优先”是硬原则。 - 本题素材源带有数据生成脚本
data.py,data/是由该脚本自造的分层数据(10 个点, 覆盖下界、 、 无解、 档、 与 顶格等), 题面为网络重建版本,与官方原题的出题意图可能存在偏差,本文结论以这组数据为准。