斐波那契串

GitHub跳转原题关系图返回列表

斐波那契串的后缀恒定、前缀只与下标奇偶有关,于是跨界匹配数按奇偶取两个定值,先暴力打出前几项再用 3x3 矩阵快速幂推到第 N 项。

OJ: roj

题目 ID: 1796

难度:提高+/省选-

标签:数学字符串矩阵快速幂KMPpython

创建: 2026-10-08 03:44

更新: 2026-10-08 03:44

形式化题目

定义 0/10/1 串序列

S0="0",S1="1",Si=Si−2 Si−1(i⩾2),S_0 = \texttt{"0"},\qquad S_1 = \texttt{"1"},\qquad S_i = S_{i-2}\,S_{i-1}\quad (i \geqslant 2),

其中 Si−2Si−1S_{i-2} S_{i-1} 表示两个串首尾相接。给定 NN、MM、PP 与一个长度恰好为 MM 的 0/10/1 串 TT,求 TT 在 SNS_N 中作为子串的出现次数(允许重叠),结果对 PP 取模。

约束为 N⩽109N \leqslant 10^9,M⩽104M \leqslant 10^4,P⩽109P \leqslant 10^9,TT 只含 0、1。

关于题面笔误。 题面把初值写成 S0="0"S_0 = \texttt{"0"}、S1="0"S_1 = \texttt{"0"},但若二者都是 "0",则所有 SiS_i 全是全零串,T="101"T = \texttt{"101"} 的出现次数恒为 00,与样例输出 88 矛盾。 真实数据中的 problem8(N=109, M=1, T="1"N = 10^9,\ M = 1,\ T = \texttt{"1"})答案也非零, 进一步排除了“全零串”的读法。因此本文按 S0="0", S1="1"S_0 = \texttt{"0"},\ S_1 = \texttt{"1"} 建模, 这正是经典的 Fibonacci word,与题面上一段 F[0]=0, F[1]=1F[0] = 0,\ F[1] = 1 的递推完全对应。

正解

思路

朴素做法与它的瓶颈。 最直接的想法是按定义把 S0,S1,…,SNS_0, S_1, \dots, S_N 拼出来, 再跑一遍 KMP 统计。等价地说就是令 F[i]F[i] = TT 在 SiS_i 中的出现次数, 对每个 ii 都重新完整匹配一次。

问题在于长度按斐波那契增长:∣Si∣=∣Si−1∣+∣Si−2∣|S_i| = |S_{i-1}| + |S_{i-2}|, i=45i = 45 时长度已越过 int 上界,N=109N = 10^9 时长度是天文数字, 显式构造在 N⩾40N \geqslant 40 之后就被彻底卡死。所以必须绕开“构造整串”。

观察一:答案可以递推。 因为 Si=Si−2Si−1S_i = S_{i-2} S_{i-1},一个匹配只有三种归宿: 完全落在左块 Si−2S_{i-2} 里、完全落在右块 Si−1S_{i-1} 里、或者跨越拼接缝。于是

fi=fi−2+fi−1+crossi.f_i = f_{i-2} + f_{i-1} + \mathrm{cross}_i .

观察二:跨界项只看两端的短片段。 若一个匹配跨越了拼接缝,它的起点必落在左块末尾 M−1M-1 个字符内、终点必落在右块开头 M−1M-1 个字符内(否则整个串就完全落进某一块了)。 所以 crossi\mathrm{cross}_i 只由 suffixM−1(Si−2)\mathrm{suffix}_{M-1}(S_{i-2}) 与 prefixM−1(Si−1)\mathrm{prefix}_{M-1}(S_{i-1}) 决定,跟两个块的全貌无关。

观察三:这两个短片段是周期的。 取最小的 KK 使 ∣SK∣⩾M−1|S_K| \geqslant M-1,则对 i⩾K+1i \geqslant K+1 这两个事实同时成立:

  • 因为 SiS_i 永远以 Si−1S_{i-1} 结尾,suffixM−1(Si)=suffixM−1(Si−1)\mathrm{suffix}_{M-1}(S_i) = \mathrm{suffix}_{M-1}(S_{i-1}) 一路传下去,后缀是一个常量;
  • 因为 SiS_i 永远以 Si−2S_{i-2} 开头,prefixM−1(Si)=prefixM−1(Si−2)\mathrm{prefix}_{M-1}(S_i) = \mathrm{prefix}_{M-1}(S_{i-2}), 前缀只与下标的奇偶有关,奇偶各有一个常量。

两者相乘,就得到本题最值钱的结论:从某个下标起,crossi\mathrm{cross}_i 只随 ii 的奇偶 取两个定值,即 crossi+2=crossi\mathrm{cross}_{i+2} = \mathrm{cross}_i。

用 T="101"T = \texttt{"101"} 验证一下,精确统计前几项得到

ii 0 1 2 3 4 5 6 7 8 9 10 11
fif_i 0 0 0 1 1 3 4 8 12 21 33 55
crossi\mathrm{cross}_i — — 0 1 0 1 0 1 0 1 0 1

crossi\mathrm{cross}_i 从 i=2i = 2 起严格按 0,1,0,1,… 交替, f7=8f_7 = 8 正是样例答案。这正是“周期 2”在起作用。

观察四:把它变成常系数递推。 取一个足够大的偶数下标 ee(保证 e⩾K+3e \geqslant K+3), 令

ak=fe+2k,bk=fe+2k+1,a_k = f_{e+2k},\qquad b_k = f_{e+2k+1},

因为 cross\mathrm{cross} 的周期为 2,两步合起来就成了不含下标依赖的常系数递推:

ak+1=fe+2k+2=fe+2k+1+fe+2k+crosse+2k+2=ak+bk+ceven,bk+1=fe+2k+3=fe+2k+2+fe+2k+1+crosse+2k+3=ak+2bk+ceven+codd, \begin{aligned} a_{k+1} &= f_{e+2k+2} = f_{e+2k+1} + f_{e+2k} + \mathrm{cross}_{e+2k+2} = a_k + b_k + c_{\text{even}},\\ b_{k+1} &= f_{e+2k+3} = f_{e+2k+2} + f_{e+2k+1} + \mathrm{cross}_{e+2k+3} = a_k + 2 b_k + c_{\text{even}} + c_{\text{odd}}, \end{aligned}

其中 ceven=crossec_{\text{even}} = \mathrm{cross}_e、codd=crosse+1c_{\text{odd}} = \mathrm{cross}_{e+1} 是两个常量。

实现细节一:两个常量由容斥反推,不手推前后缀。 直接把 S0…Se+1S_0 \dots S_{e+1} 老老实实 拼出来(此时 e⩽K+5⩽25e \leqslant K+5 \leqslant 25,长度最多几万),用 KMP 得到精确的 f0…fe+1f_0 \dots f_{e+1},再令

ceven=fe−fe−1−fe−2,codd=fe+1−fe−fe−1,c_{\text{even}} = f_e - f_{e-1} - f_{e-2},\qquad c_{\text{odd}} = f_{e+1} - f_e - f_{e-1},

这正是把递推式移项后的结果,比手写前后缀匹配短得多,也不容易错。

实现细节二:临界值不能取小。 前缀“按奇偶稳定”需要 i⩾K+2i \geqslant K+2, 为了同时对 ee 和 e+1e+1 生效(两者奇偶不同,各自要一个稳定前缀), 必须取 e⩾K+3e \geqslant K+3。KK 由 ∣SK∣⩾M−1|S_K| \geqslant M-1 定出:验证时我们仍暴力构造, 所以只需求出 KK 后多拼几项即可。

实现细节三:矩阵快速幂。 把 (ak,bk,1)(a_k, b_k, 1) 当作状态列向量,转移矩阵

A=[11ceven12ceven+codd001].A = \begin{bmatrix} 1 & 1 & c_{\text{even}}\\ 1 & 2 & c_{\text{even}} + c_{\text{odd}}\\ 0 & 0 & 1 \end{bmatrix}.

对指数 k=⌊(N−e)/2⌋k = \lfloor (N - e)/2 \rfloor 做快速幂,再从初始向量 (a0,b0,1)=(fe,fe+1,1)(a_0, b_0, 1) = (f_e, f_{e+1}, 1) 推出答案:N≡e(mod2)N \equiv e \pmod 2 时取第一行, 否则取第二行。

小 NN 的处理。 若 N⩽K+5N \leqslant K+5,此时 ∣SN∣|S_N| 本身很小,前面暴力打的那张表里 就有 fNf_N,直接输出即可,不需要走矩阵。M=1M = 1 时 M−1=0M-1 = 0,K=0K = 0, cross\mathrm{cross} 恒为 00,本流程照常工作(problem8 就是 M=1M = 1 的顶格点)。

代码

Python 版(functools 都没用上,全部按表达式写):

python
#!/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 承接模数乘法):

cpp
// 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;
}

复杂度

  • 时间:构造串到 SK+5S_{K+5} 需要 O(∣SK+5∣)O(|S_{K+5}|),其中 ∣SK+5∣=O(M)|S_{K+5}| = O(M)(KK 的定义 决定了 ∣SK∣|S_K| 是首个 ⩾M−1\geqslant M-1 的斐波那契长度,∣SK+5∣<13M|S_{K+5}| < 13M); KMP 统计同样 O(M)O(M),因为只需对前常数个串各跑一次。矩阵快速幂是 O(33log⁡N)O(3^3 \log N)。整体 O(M+log⁡N)O(M + \log N),M=104M = 10^4、N=109N = 10^9 时实测 10 ms (限时 1000 ms)。
  • 空间:字符串存到 SK+5S_{K+5} 为止,O(M)O(M);矩阵与状态是常数级。实测峰值 8.3 MB(限时 256 MB)。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两种语言版本, 复杂度完全同阶。Python 侧省去了 C++ 里的 __int128——Python 整数天然无溢出, 矩阵乘法直接乘再取模即可。

总结

  • 递推的目标是“消灭下标依赖”。fi=fi−2+fi−1+crossif_i = f_{i-2} + f_{i-1} + \mathrm{cross}_i 本身 并不是常系数递推,因为 crossi\mathrm{cross}_i 随 ii 变;发现它周期为 2 之后, 两步一合并才拿到可以快速幂的常系数形式。
  • 周期性的来源是“两端稳定”:斐波那契串永远以 Si−1S_{i-1} 结尾、以 Si−2S_{i-2} 开头, 于是长为 M−1M-1 的后缀冻结成常量、前缀按奇偶分裂成两个常量。 这是本题从“无法构造的无穷串”跳到“有限状态”的桥梁。
  • 跨界项不必手推前后缀:c=fi−fi−1−fi−2c = f_i - f_{i-1} - f_{i-2} 是递推式移项的直接产物, 比显式 KMP 匹配前后缀更短、更不易错,也让 M=1M = 1 这类退化情形自动成立。
  • 初值必须按样例修正:题面写 S1="0"S_1 = \texttt{"0"} 与样例输出 88 矛盾, 真实数据也否定了全零读法,故取 S1="1"S_1 = \texttt{"1"}。读题时“样例优先”是硬原则。
  • 本题素材源带有数据生成脚本 data.py,data/ 是由该脚本自造的分层数据(10 个点, 覆盖 NN 下界、P=1P = 1、M>∣SN∣M > |S_N| 无解、30%/60%30\%/60\% 档、NN 与 MM 顶格等), 题面为网络重建版本,与官方原题的出题意图可能存在偏差,本文结论以这组数据为准。