自动搬运

查看原文

来自洛谷，原作者为

	LRH 我想知道这个世界到底是怎么样的，我想知道距离足够远的时候它们的声音还能不能入我的耳

搬运于2025-08-24 22:59:22，当前版本为作者最后更新于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;
}