社区讨论

求助关于语法

学术版参与者 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 的
但是我在本地测试的过程中,输入如下样例:
CPP
input:

10 4 1
AGCAATTCAT
ACAT

output:

3
却没有输出
我又尝试了题解的代码,也有同样的问题
请问这是什么原因?

回复

13 条回复,欢迎继续交流。

正在加载回复...