样例未过求调

[stringdp100005]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int fac[300005], inv[300005], len, ans;
unsigned long long hashp[300005], hashb[300005], pw[300005];
unordered_map<unsigned long long, int> hs_t;
string s;
int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i <= 300000; i++) fac[i] = fac[i - 1] * i % mod;
	inv[300000] = qpow(fac[300000], mod - 2);
	for (int i = 299999; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
	pw[0] = 1;
	for (int i = 1; i <= len; i++) pw[i] = pw[i - 1] * 131;
	for (int i = 1; i <= len; i++) hashp[i] = hashp[i - 1] * 131 + s[i];
	for (int i = len; i >= 1; i--) hashb[i] = hashb[i + 1] * 131 + s[i]; 
}
unsigned long long gethash1(int l, int r) {
	return hashp[r] - hashp[l - 1] * pw[r - l + 1];
}
signed main() {
	cin >> s;
	len = s.size(); s = ' ' + s; 
	init();
	for (int i = 1; i <= len; i++) {
		hs_t.clear();
		int k = len / i;
		for (int j = 1; j <= k; j++) {
			int st = i * (j - 1) + 1, ed = st + i - 1;
			hs_t[gethash1(st, ed)]++;
		}
		int res = fac[k];
		for (auto x : hs_t) res = res * inv[x.second] % mod;
		if (len % i != 0) {
			hs_t.clear();
			int bk = len - k * i + 1;
			for (int j = 1; j <= k; j++) {
				int st = bk + (j - 1) * i, ed = st + i - 1;
				hs_t[gethash1(st, ed)]++;
			}	
			int res2 = fac[k];
			for(auto x : hs_t) res2 = res2 * inv[x.second] % mod;
			ans = (ans + res + res2) % mod;	
		} else ans = (ans + res) % mod;
	}
	cout << ans;
	return 0;
}

[2345安全卫士 (蛋小黄（蒟蒻）)]

这是哪题啊？

[吴梓峤]

是T8