我康康
- 从 1 到 n/2 因为 x > m 。
- 对于每个 x ，计算可以形成的不同子串的数量。
- 对于每个 x ，使用哈希表存储所有可能的子串的哈希值，以快速检查两个子串是否相同。
- 将所有可能的 x 对应的组合数量累加，并在最后对 998244353 取模。
膜拜大佬%%%
%%%%%%tql
最后的结果怎么算？枚举 i ，算出 \dfrac{n}{i}! 除以每个字符串的出现次数的阶乘之积？
好像有思路了，那不能整除的时候怎么办？
又有思路了，可不可以前后缀各跑一遍？
就按我的思路就行了，不用管
怎么存储所有子串啊，比方说 aab，有两种分割方式（a|ab，aa|b）长度一大情况就多了啊
应该是可以的
unordered_map 怎么清空啊
bdfs
题目链接
我没有权限
样例二给我一下
给我样例
这份代码我已经找出三处错误了
ababccd
661
再放一份代码：
#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];
}
unsigned long long gethash2(int l, int r) {
return hashb[l] - hashb[r + 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();
for (int j = k; j >= 1; j--) {
int ed = i * j, st = ed - i + 1;
hs_t[gethash2(st, ed)]++;
}
int res2 = fac[k];
for(auto x : hs_t) res2 = res2 * inv[x.second] % mod;
ans = (ans + res + res2) % mod;
cout << res + res2 << " ";
} else ans = (ans + res) % mod;
}
cout << ans;
return 0;
}
样例二的输出就差一点