社区讨论
求助关于语法
学术版参与者 6已保存回复 13
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 13 条
- 当前快照
- 1 份
- 快照标识符
- @lvjg9v8g
- 此快照首次捕获于
- 2024/04/28 19:31 2 年前
- 此快照最后确认于
- 2024/04/28 21:24 2 年前
我在做 这道题 的过程中,写出了如下代码
CPP#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) % 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 = 0; i <= n + m - 2; ++ i)
ans += (cnt[i] == m);
return printf ("%lld\n", ans), 0;
}
提交后以及在洛谷 IDE 中,这份代码都是 AC 的
但是我在本地测试的过程中,输入如下样例:
CPPinput:
10 4 1
AGCAATTCAT
ACAT
output:
3
却没有输出
我又尝试了题解的代码,也有同样的问题
请问这是什么原因?
回复
共 13 条回复,欢迎继续交流。
正在加载回复...