QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22583#2841. 赛艇blackswallow#AC ✓1824ms227896kbC++204.5kb2022-03-09 22:06:582022-04-30 01:24:24

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:24:24]
  • 评测
  • 测评结果:AC
  • 用时:1824ms
  • 内存:227896kb
  • [2022-03-09 22:06:58]
  • 提交

answer

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 1510;
const int SIZ = (1 << 23) + 10;
const int MAXK = 5e6 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
const int GG = 3;
//const int base = 131;

int n, m, k, Ans, blen;
int sL[MAXN], sR[MAXN], sum[MAXN][MAXN];
int F[SIZ], G[SIZ];
int rev[SIZ], ll, lim, ilim, Gi, Gp[SIZ], iGp[SIZ];
char mmp[MAXN][MAXN], mv[MAXK];
bool tmp[MAXN << 1][MAXN << 1];

template<typename T> inline bool read(T &a) {
	a = 0; char c = getchar(); int f = 1;
	while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
	return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

int qpow(int x, int b) {
	int res = 1;
	for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
	return res;
}

void Init(int x) {
	lim = 1, ll = 0;
	while(lim < x) lim <<= 1, ++ll;
	ilim = inv(lim), Gi = inv(GG);
	for(int i = 0; i < lim; ++i)
		rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (ll - 1)));
	for(int mid = 1; mid < lim; mid <<= 1) {
		Gp[mid] = qpow(GG, (mod - 1) / (mid << 1));
		iGp[mid] = qpow(Gi, (mod - 1) / (mid << 1));
	}
}

void format(int x) {
	lim = 1, ll = 0;
	while(lim < x) lim <<= 1, ++ll;
	ilim = inv(lim);
	for(int i = 0; i < lim; ++i)
		rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (ll - 1)));
}

void NTT(int *A, int opt) {
	for(int i = 0; i < lim; ++i)
		if(rev[i] < i) swap(A[i], A[rev[i]]);
	for(int mid = 1, w; mid < lim; mid <<= 1) {
		w = (opt == 1) ? Gp[mid] : iGp[mid];
		for(int i = 0, x, y, now; i < lim; i += (mid << 1)) {
			now = 1;
			for(int j = 0; j < mid; ++j, now = now * w % mod) {
				x = A[i + j], y = A[i + j + mid] * now % mod;
				A[i + j] = x + y, A[i + j + mid] = x - y + mod;
			}
		}
		if(mid == 512 || mid == 512 * 512)
			for(int i = 0; i < lim; ++i) A[i] %= mod;
	}
	for(int i = 0; i < lim; ++i) A[i] %= mod;
	if(opt == 1) return;
	for(int i = 0; i < lim; ++i) A[i] = A[i] * ilim % mod;
}

signed main () {
#ifdef FILE
	freopen("19.in", "r", stdin);
	freopen("B.out", "w", stdout);
#endif
	read(n), read(m), read(k);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", mmp[i] + 1);
		for(int j = 1; j <= m; ++j) {
			sum[i][j] = mmp[i][j] - '0';
			F[(i - 1) * m + (j - 1)] = mmp[i][j] - '0';
		}
	}
	scanf("%s", mv + 1);
	int curx = n, cury = m;
	tmp[curx][cury] = true;
	for(int i = 1; i <= k; ++i) {
		if(mv[i] == 'w') curx--;
		if(mv[i] == 'a') cury--;
		if(mv[i] == 's') curx++;
		if(mv[i] == 'd') cury++;
		tmp[curx][cury] = true;
	}
	int H = 0, mn = INF, len = 0;
	for(int i = 0, sum; i < (MAXN << 1); ++i) {
		sum = 0;
		for(int j = 0; j < (MAXN << 1); ++j)
			sum += tmp[i][j];
		if(!sum) continue;
		++H; sL[H] = -1;
		for(int j = 0; j < (MAXN << 1); ++j) {
			if(!tmp[i][j]) continue;
			if(sL[H] == -1) sL[H] = j;
			sR[H] = j;
		}
	}
	for(int i = 1; i <= H; ++i) mn = min(mn, sL[i]);
	for(int i = 1; i <= H; ++i) {
		sL[i] -= mn, sR[i] -= mn;
		len = max(len, sR[i] + 1);
	}
	for(int i = 0, t = 0, cc = 0; i < (MAXN << 1); ++i) {
		t = 0;
		for(int j = 0; j < (MAXN << 1); ++j) t += tmp[i][j];
		if(!t) continue;
		for(int j = 0; j < (MAXN << 1); ++j) {
			if(!tmp[i][j]) continue;
			//cerr << cc << ' ' << j - mn << endl;
			G[(n - cc) * m + (m - (j - mn))] = 1;
			//V[cc].set(j - mn);
		}
		++cc;
	}
	/*for(int i = 0; i <= n * m; ++i)
		cout << F[i] << ' ';
	cout << endl;
	for(int i = 0; i <= n * m; ++i)
		cout << G[i] << ' ';
	cout << endl;*/
	Init(((n + 1) * (m + 1)) << 1);
	NTT(F, 1), NTT(G, 1);
	for(int i = 0; i < lim; ++i) F[i] = F[i] * G[i] % mod;
	NTT(F, -1);
	for(int i = 0; i < n - H + 1; ++i) {
		for(int j = 0; j < m - len + 1; ++j) {
			if(!F[(n + i) * m + (m + j)]) {
				//cout << i + 1 << ' ' << j + 1 << endl;
				++Ans;
			}
		}
	}
	printf("%lld\n", Ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 20220kb

input:

5 5 5
00000
10000
00000
00000
01001
awdsw

output:

11

result:

ok single line: '11'

Test #2:

score: 0
Accepted
time: 87ms
memory: 31840kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

77549

result:

ok single line: '77549'

Test #3:

score: 0
Accepted
time: 83ms
memory: 30792kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #4:

score: 0
Accepted
time: 93ms
memory: 30984kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #5:

score: 0
Accepted
time: 82ms
memory: 31596kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #6:

score: 0
Accepted
time: 87ms
memory: 31740kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #7:

score: 0
Accepted
time: 397ms
memory: 70668kb

input:

1000 1000 300000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

83496

result:

ok single line: '83496'

Test #8:

score: 0
Accepted
time: 402ms
memory: 74348kb

input:

1000 1000 1000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

63001

result:

ok single line: '63001'

Test #9:

score: 0
Accepted
time: 375ms
memory: 69756kb

input:

1000 1000 1500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

62500

result:

ok single line: '62500'

Test #10:

score: 0
Accepted
time: 1804ms
memory: 227624kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #11:

score: 0
Accepted
time: 1806ms
memory: 227896kb

input:

1500 1500 5000000
100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...

output:

22801

result:

ok single line: '22801'

Test #12:

score: 0
Accepted
time: 6ms
memory: 20168kb

input:

2 2 4
00
01
dada

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 1824ms
memory: 227576kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #14:

score: 0
Accepted
time: 1749ms
memory: 224668kb

input:

1500 1500 2250
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

140625

result:

ok single line: '140625'

Test #15:

score: 0
Accepted
time: 13ms
memory: 20208kb

input:

50 60 20
000000000000000000000000010000000000000000000010000000000000
000000000000000000000000000000000000000000000000010000000000
000000000000000000000000000000000000000000010000000000001000
000000000000000000000000000000000100000000000000010000000000
00000000010000000000000000000000000000000000000...

output:

1633

result:

ok single line: '1633'

Test #16:

score: 0
Accepted
time: 14ms
memory: 24248kb

input:

60 50 500
00000000000000000000001000000000000000000100000000
00000000000000000000000010000000001000000000000000
00000000000000000000000000000000000000000000100000
00000000000000000000000000001000000000000010000000
00000000010000000000000000000000000000000000000000
00000000000000000000000000000000000...

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 95ms
memory: 34076kb

input:

500 500 500000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15876

result:

ok single line: '15876'

Test #18:

score: 0
Accepted
time: 86ms
memory: 30956kb

input:

500 500 500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

228475

result:

ok single line: '228475'

Test #19:

score: 0
Accepted
time: 90ms
memory: 31580kb

input:

500 500 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

53530

result:

ok single line: '53530'

Test #20:

score: 0
Accepted
time: 81ms
memory: 29224kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 83ms
memory: 30928kb

input:

500 500 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

9699

result:

ok single line: '9699'