这份代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define Mod (998244353)
#define INF (0x3f3f3f3f)
using namespace std;
inline int fsp(int x, int p) {
int res = 1;
for (; p; p >>= 1) {
if (p & 1) res = res * x % Mod;
x = x * x % Mod;
}
return res;
}
const int MAXN = 1000005;
const int G = 3, InvG = 332748118;
int n, m, K;
char s[MAXN], t[MAXN];
int ans, cnt[MAXN];
struct Poly {
int len, inv, a[MAXN], rev[MAXN];
inline Poly(int ln, int l) {
len = ln, -- l, inv = fsp(len, Mod - 2);
memset(a, 0, sizeof(a));
memset(rev, 0, sizeof(rev));
for (int i = 1; i <= len; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l);
}
inline void ntt(int typ) {
for (int i = 1; i < len; ++ i)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int flr = 2; flr <= len; flr <<= 1) {
int Wn = fsp(typ == 1 ? G : InvG, (Mod - 1) / flr);
for (int mid = flr >> 1, l = 0; l < len; l += flr) {
int w = 1, x, y;
for (int i = l; i < l + mid; ++ i, w = w * Wn % Mod)
x = a[i], y = w * a[i + mid] % Mod,
a[i] = (x + y) % Mod, a[i + mid] = (x - y) % Mod;
}
}
}
};
inline Poly operator * (Poly &A, Poly &B) {
int len = 1, l = 0;
while (len <= n + m - 2) ++ l, len <<= 1;
Poly C(len, l); A.ntt(1); B.ntt(1);
for (int i = 0; i <= C.len; ++ i)
C.a[i] = A.a[i] * B.a[i];
C.ntt(-1);
for (int i = 0; i <= C.len; ++ i)
C.a[i] = C.a[i] * C.inv % Mod;
return C;
}
inline void Solve(char c) {
int len = 1, l = 0;
while (len <= n + m - 2) ++ l, len <<= 1;
Poly f(len, l), g(len, l);
for (int i = 0, lst = -INF; i < n; ++ i) {
if (s[i] == c) lst = i;
f.a[i] |= (i - lst <= K);
}
for (int i = n - 1, lst = INF; ~i; -- i) {
if (s[i] == c) lst = i;
f.a[i] |= (lst - i <= K);
}
for (int i = 0; i < m; ++ i)
g.a[i] = (t[m - i - 1] == c);
f = f * g;
for (int i = 0; i < f.len; ++ i)
cnt[i] += f.a[i];
}
signed main()
{
scanf ("%lld%lld%lld", &n, &m, &K);
scanf ("%s%s", s, t);
for (int i = 0; i < 4; ++ i) Solve("ACTG"[i]);
for (int i = 1; i <= n + m - 2; ++ i)
ans += (cnt[i] == m);
return printf ("%lld\n", ans), 0;
}
我在本地一直无法运行,这道题的题解也不行,其他题目代码都可以。
并且测试了这份代码可以在洛谷 IDE 上运行
请问它有什么问题/特别之处吗?