思路与算法

维护每个Si的模式出现数及长度至多M−1的前缀、后缀。拼接时总数=两个子串内部次数+跨界次数，跨界只需KMP扫描左后缀与右前缀的连接。长串前缀按奇偶周期2，后缀稳定；M≤10000时到40项之前已经稳定，后续跨界次数周期2。把连续两步合为3×3仿射矩阵，快速幂跳至N。

正确性说明

出现位置唯一属于左内部、右内部或跨界三类；跨界模式长度M，所以两侧最多各M−1字符足够，KMP统计包含全部重叠匹配。两子串均长于M−1后，pref_i=pref_i−2而suf_i=suf_i−1，故最终前缀周期2、后缀不变，跨界项也周期2。计算到40项足以越过所有M≤10000的稳定阈值；随后两种递推矩阵按正确顺序合并，快速幂保持计数对P的余数。

复杂度

模式失败数组O(M)，40次边界拼接扫描O(40M)，矩阵幂O(log N)，空间O(40M)（可进一步只存常数个边界串）；初始化和输入O(M)。

易错点

初值修订为S0=0,S1=1，否则101样例不可能为8。统计允许重叠；M1没有跨界匹配，截断长度为0。拼接顺序是Si−2在左、Si−1在右，矩阵两步相乘也有顺序；P1答案0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod;
struct Mat {
    ll a[3][3]{};
};
Mat mul(Mat x, Mat y) {
    Mat z;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
    return z;
}
Mat trans(ll c) {
    Mat z;
    z.a[0][0] = z.a[0][1] = z.a[1][0] = z.a[2][2] = 1 % mod;
    z.a[0][2] = c;
    return z;
}
int main() {
    ll N;
    int m;
    string t;
    cin >> N >> m >> mod >> t;
    vector<int> pi(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j && t[i] != t[j])
            j = pi[j - 1];
        if (t[i] == t[j])
            j++;
        pi[i] = j;
    }
    auto count = [&](const string &s, int boundary) {
        ll z = 0;
        for (int i = 0, j = 0; i < (int)s.size(); i++) {
            while (j && s[i] != t[j])
                j = pi[j - 1];
            if (s[i] == t[j])
                j++;
            if (j == m) {
                if (boundary < 0 || (i - m + 1 < boundary && i >= boundary))
                    z++;
                j = pi[j - 1];
            }
        }
        return z % mod;
    };
    int cap = m - 1;
    vector<string> pre(43), suf(43);
    vector<ll> cnt(43), cross(43);
    pre[0] = suf[0] = "0";
    pre[1] = suf[1] = "1";
    cnt[0] = count("0", -1);
    cnt[1] = count("1", -1);
    if (!cap) {
        pre[0] = pre[1] = suf[0] = suf[1] = "";
    }
    for (int i = 2; i <= 42; i++) {
        string s = suf[i - 2] + pre[i - 1];
        cross[i] = count(s, suf[i - 2].size());
        cnt[i] = (cnt[i - 2] + cnt[i - 1] + cross[i]) % mod;
        string p = pre[i - 2] + pre[i - 1];
        pre[i] = p.substr(0, cap);
        string q = suf[i - 2] + suf[i - 1];
        suf[i] = q.size() > (size_t)cap ? q.substr(q.size() - cap) : q;
    }
    if (N <= 40) {
        cout << cnt[N] << '\n';
        return 0;
    }
    Mat one = trans(cross[41]), two = trans(cross[42]), power = mul(two, one), acc;
    for (int i = 0; i < 3; i++)
        acc.a[i][i] = 1 % mod;
    ll k = (N - 40) / 2;
    for (; k; k >>= 1, power = mul(power, power))
        if (k & 1)
            acc = mul(power, acc);
    if ((N - 40) & 1)
        acc = mul(one, acc);
    cout << (acc.a[0][0] * cnt[40] + acc.a[0][1] * cnt[39] + acc.a[0][2]) % mod << '\n';
}