QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22588#2841. 赛艇lindongli2004#WA 594ms292764kbC++144.4kb2022-03-09 23:24:592022-04-30 01:25:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:25:09]
  • 评测
  • 测评结果:WA
  • 用时:594ms
  • 内存:292764kb
  • [2022-03-09 23:24:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

const int MAXN = 4100, Mod = 998244353;
inline void reset(int *f, int n) {memset(f, 0, n << 3);}
inline void copy(int *f, int *g, int n) {memcpy(g, f, n << 3);}
inline int chkadd(int x) {return x >= Mod? x - Mod : x;}
inline int chksub(int x) {return x < 0? x + Mod : x;}
inline int fastpow(int x, int p) {
	int ans = 1;
	while (p) {
		if (p & 1) ans = ans * x % Mod;
		x = x * x % Mod;
		p >>= 1;
	}
	return ans;
}

namespace ntt {
	const int G = 3;
	int rev[MAXN + 10], w1[MAXN + 10], w2[MAXN + 10], revn;
	inline int calc(int n) {return 1 << (int)ceil(log2(n));}
	void init(int n) {
		revn = n;
		w1[0] = 1, w1[1] = fastpow(G, (Mod - 1) / n);
		w2[0] = 1, w2[n - 1] = w1[1]; rev[1] = n >> 1;
		for (int i = 2; i < n; ++i) {
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1)? n >> 1 : 0);
			w1[i] = w1[i - 1] * w1[1] % Mod;
			w2[n - i] = w1[i];
		}
	}

	void NTT(int *f, int n, int op) {
		int kk = log2(revn / n);
		for (int i = 0; i < n; ++i)
			if (i > (rev[i] >> kk)) swap(f[i], f[rev[i] >> kk]);

		int *ome = op? w2 : w1, res = revn >> 1;
		for (int p = 2; p <= n; p <<= 1, res >>= 1) {
			int len = p >> 1;
			for (int k = 0; k < n; k += p) {
				int *o = ome;
				for (int l = k; l < k + len; ++l) {
					int tmp = f[l + len] * *o % Mod;
					f[l + len] = chksub(f[l] - tmp);
					f[l] = chkadd(f[l] + tmp);
					o += res;
				}
			}
		}
		if (op) {
			for (int i = 0; i < n; ++i)
				f[i] = f[i] * op % Mod;
		}
	}

	void MUL(int *a, int *b, int *c, int n, int m, int res) {
		static int f[MAXN + 10], g[MAXN + 10], invn;
		copy(a, f, n); copy(b, g, m);
		m += n; n = calc(m); invn = fastpow(n, Mod - 2);
		NTT(f, n, 0), NTT(g, n, 0);
		for (int i = 0; i < n; ++i) f[i] = f[i] * g[i] % Mod;
		NTT(f, n, invn);
		copy(f, c, res);
		reset(f, n); reset(g, n);
	}
}

using ntt :: init;
using ntt :: calc;
using ntt :: MUL;
using ntt :: NTT;
const int MAXK = 5e6;
int f[MAXN + 10][MAXN + 10], g[MAXN + 10][MAXN + 10], ans[MAXN + 10][MAXN + 10];
int a[MAXN + 10][MAXN + 10];
char str[MAXK + 10];

pii sta[MAXK + 10];
signed main() {
	//freopen ("std.in", "r", stdin);
	//freopen ("std.out", "w", stdout);
	int n, m, K;
	n = read(), m = read(), K = read();
	int nn = calc(2*max(n+1,m+1)), inv = fastpow(nn, Mod - 2);
	init(nn);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", str + 1);
		for (int j = 1; j <= m; ++j) {
			ans[i][j] = a[i][j] = str[j] == '1';
		}
	}
	scanf("%s", str + 1);
	int px = 0, py = 0;
	for (int i = 0; i <= m + 1; ++i) a[0][i] = a[n + 1][i] = 1;
	for (int i = 0; i <= n + 1; ++i) a[i][0] = a[m + 1][i] = 1;
	for (int i = 1; i <= K; ++i) {
		if (str[i] == 'w') ++px;
		else if (str[i] == 's') --px;
		else if (str[i] == 'a') ++py;
		else if (str[i] == 'd') --py;
		sta[i] = mkp(px, py);
	}
	for (int ty = 0; ty < 4; ++ty) {
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		for (int i = 0; i <= n + 1; ++i)
			for (int j = 0; j <= m + 1; ++j) {
				int x = ty & 1? n - i + 1 : i;
				int y = ty & 2? m - j + 1 : j;
				f[x][y] = a[i][j];
			}
		static int c[MAXN + 10], d[MAXN + 10];
		for (int i = 1; i <= K; ++i) {
			int x = sta[i].fi, y = sta[i].se;
			x = ty & 1? -x : x;
			y = ty & 2? -y : y;
			if (x < 0 || y < 0) continue;
			g[x][y] = 1;
		}
		for (int i = 0; i < nn; ++i) {
			NTT(f[i], nn, 0);
			NTT(g[i], nn, 0);
		}
		for (int j = 0; j < nn; ++j) {
			memset(c, 0, sizeof(c));
			memset(d, 0, sizeof(d));
			for (int i = 0; i < nn; ++i) c[i] = f[i][j];
			for (int i = 0; i < nn; ++i) d[i] = g[i][j];
			NTT(c, nn, 0);
			NTT(d, nn, 0);
			for (int i = 0; i < nn; ++i) c[i] = c[i] * d[i] % Mod;
			NTT(c, nn, inv);
			for (int i = 0; i < nn; ++i) f[i][j] = c[i];
		}
		for (int i = 0; i < nn; ++i) NTT(f[i], nn, inv);
		for (int i = 0; i <= n + 1; ++i)
			for (int j = 0; j <= m + 1; ++j) {
				int x = ty & 1? n - i + 1 : i;
				int y = ty & 2? m - j + 1 : j;
				ans[x][y] |= f[i][j];
			}
	}
	int Ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			Ans += !ans[i][j];
	cout << Ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 151ms
memory: 273976kb

input:

5 5 5
00000
10000
00000
00000
01001
awdsw

output:

11

result:

ok single line: '11'

Test #2:

score: -100
Wrong Answer
time: 594ms
memory: 292764kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

78729

result:

wrong answer 1st lines differ - expected: '77549', found: '78729'