题解：P10581 [蓝桥杯 2024 国 A] 重复的串

SleepinGod · 2025-07-19 13:11:36 · 题解

• 题意

  求出长度为n且恰好出现两次原串的字符串个数

• 思路

  我们可以定义状态 {f_{l,e,i}} 表示当前字符串长度为 l 匹配了 e 次已经匹配到了第 i 位的方案数

  匹配问题我们自然可以想到使用 KMP 来做这件事

  所以我们可以枚举当前填的字母并完成转移，如何转移这里读者可以思考一会

  我们可以很自然的发现 f_{l,e,i} 只从长度为 l-1 的状态转移而来，并且每次转移的方式都是一样的。所以我们考虑使用矩阵乘法优化这个转移

  我们可以枚举当前已经匹配到了第 i 位，匹配了e 次，下一个字母填什么，然后使用 kmp 得到它可以转移到的状态匹配到了第多少位，匹配了多少次。

  我们可以赋给每种这样的状态一个下标，如果 j 可以转化到 k 那么图大概长这样

  所以我们可以发现每一次转移都乘上了这个中间的矩阵,故我们可以使用矩阵快速幂解决这个问题

• 代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 105, mod = 998244353;

int n, m, len, nxt[N];

string s;

struct S {
    ll a[N][N];
} dis, ans;

S operator * (const S &A, const S &B) {
    S C;
    for (ll i = 0; i <= m; i++) {
        for (ll j = 0; j <= m; j++) {
            ll s = 0;
            for (ll k = 0; k <= m; k++) {
                s = (A.a[i][k] * B.a[k][j] % mod + s) % mod;
            }
            C.a[i][j] = s;
        }
    }
    return C;
} //矩阵乘法 

int id(int x, int y) {
    return y * (len + 1) + x;
}  //赋予一个状态编号 

void D(int x) {
    ans.a[0][0] = 1; //初始只有转移到0匹配了0次才是1 
    for (; x; x /= 2, dis = dis * dis) {
        if (x & 1) {
            ans = ans * dis;
        }
    }
}

int main() {
    cin >> s >> n;
    len = s.size();
    s = " " + s + "*";

    for (int i = 2, j = 0; i <= len; i++) {
        for (; j && s[i] != s[j + 1]; j = nxt[j]) {
        }
        j = nxt[i] = j + (s[i] == s[j + 1]);
    }

    //kmp模板 

    m = 3 * (len + 1);

    //注意这里是len+1因为是从0到len的

    for (int i = 0; i <= len; i++) {    //枚举匹配到的位置 
        for (int e = 0; e <= 2; e++) {  //枚举匹配的次数 
            for (char ch = 'a'; ch <= 'z'; ch++) { //枚举下一个字母 
                int j = i;
                for (; j && ch != s[j + 1]; j = nxt[j]) {
                }               
                j += (ch == s[j + 1]); // 算出下一个状态匹配到的位置 
                if (j == len) {
                    if (e == 2) {
                        continue;
                    }                 //我们需要的是恰好两次故超过的不算 
                    dis.a[id(i, e)][id(j, e + 1)]++;
                } else {
                    dis.a[id(i, e)][id(j, e)]++;
                }
            }
        }
    }

    D(n);
    ll sum = 0; 
    for (int i = 0; i <= len; i++) {
        sum += ans.a[0][i + (2 * (len + 1))];  
        sum %= mod;
    } //统计答案 

    cout << sum % mod;
    return 0;
}