QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21611#2841. 赛艇hy_zheng_zai_nei_juan#AC ✓2267ms266420kbC++204.3kb2022-03-07 16:35:292022-05-08 03:42:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:42:39]
  • 评测
  • 测评结果:AC
  • 用时:2267ms
  • 内存:266420kb
  • [2022-03-07 16:35:29]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e7 + 50;
const int mod = 998244353;
const int g = 3;

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int fastpow(int x, int p)
{
	int r = 1;
	while (p)
	{
		if (p & 1) r = mul(r, x);
		x = mul(x, x);
		p >>= 1;
	}
	return r;
}

struct NTT
{
	int omega[N], omegaInv[N], rev[N], len, k;
	inline void init(int n)
	{
		len = 1, k = 0;
		while (len <= n) len <<= 1, ++k;
		for (int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		const int t = fastpow(g, (mod - 1) / len);
		omega[0] = omegaInv[0] = 1;
		for (int i = 1; i < len; ++i) omega[i] = omegaInv[len - i] = mul(omega[i - 1], t);
	}
	inline void DFT(int *a, const int *w)
	{
		for (int i = 1; i < len; ++i) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
		for (int h = 1; h < len; h <<= 1)
			for (int t = len / (h << 1), j = 0; j < len; j += (h << 1))
			{
				const int *wn = w; int *x = a + j, *y = a + j + h;
				for (int i = j; i < j + h; ++i)
				{
					int _1 = *x, _2 = mul(*y, *wn);
					*x++ = inc(_1, _2);
					*y++ = dec(_1, _2);
					wn += t;
				}
			}
		if (w == omegaInv)
		{
			const int t = mod - (mod - 1) / len;
			for (int i = 0; i < len; ++i) a[i] = mul(a[i], t);
		}
	}
	inline void operator()(std::vector<int> &_, int op)
	{
		if (_.size() < len) _.resize(len);
		if (op == 1) DFT(_.data(), omega);
		else DFT(_.data(), omegaInv);
		assert(_.size() >= len);
	}
} ntt;

struct Poly
{
	std::vector<int> _;
	Poly(){}
	Poly(const std::vector<int> &_) : _(_) {}
	inline int& operator[](int k)
	{
		if (_.size() <= k) _.resize(k + 1);
		return _[k];
	}
	inline int operator[](int k) const
	{
		if (_.size() <= k) return 0;
		return _[k];
	}
	inline int deg() const
	{
		return (int)_.size() - 1;
	}
};


template <int T>
struct fast_io
{
	char p[T], q[T], * p1, * p2, * q1, * q2;
	fast_io()
	{
		p1 = p2 = p;
		q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char c)
	{
		if (q1 == q2) q2 = (q1 = q) + fwrite(q, 1, T, stdout);
		*q1++ = c;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1 << 20> io;
inline int read()
{
	int res = 0;
	char ch;
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return res;
}
inline void put(int64_t x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) put(x / 10);
	io.pc(48 + x % 10);
}
inline void output(int64_t x, char ch = ' ')
{
	put(x);
	io.pc(ch);
}

inline Poly operator*(const Poly &A, const Poly &B)
{
	int d1 = A.deg(), d2 = B.deg();
	std::vector<int> a = A._, b = B._;
	ntt.init(d1 + d2 + 1);
	ntt(a, 1), ntt(b, 1);
	std::vector<int> c(ntt.len);
	for (int i = 0; i < ntt.len; ++i) c[i] = mul(a[i], b[i]);	
	ntt(c, -1);
	return Poly(c);
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	Poly A, B;
	int n, m, k;
	std::cin >> n >> m >> k;
	std::string s;
	auto id = [&](int i, int j) {
		return (i - 1) * m + j;
	};
	auto dir = [&](char ch) -> std::pair<int, int> {
		if (ch == 's') return {1, 0};
		if (ch == 'w') return {-1, 0};
		if (ch == 'd') return {0, 1};
		if (ch == 'a') return {0, -1};
		throw;
	};
	for (int i = 1; i <= n; ++i) {
		std::cin >> s;
		for (int j = 1; j <= m; ++j) {
			A[id(i, j)] = (s[j - 1] == '1');
		}
	}
	std::cin >> s;
	int len = s.length();
	int curx = 1, cury = 1;
	int minx = 1, miny = 1;
	for (int i = 0; i < len; ++i) {
		auto [x, y] = dir(s[i]);
		curx += x, cury += y;
		minx = std::min(minx, curx);
		miny = std::min(miny, cury);
	}
	int tx = 2 - minx, ty = 2 - miny;
	int maxx = tx, maxy = ty;
	B[n * m - id(tx, ty) + 1] = 1;
	curx = tx, cury = ty;
	for (int i = 0; i < len; ++i) {
		auto [x, y] = dir(s[i]);
		curx += x, cury += y;
		maxx = std::max(maxx, curx);
		maxy = std::max(maxy, cury);
		B[n * m - id(curx, cury) + 1] = 1;
	}
	Poly C = A * B;
	int ans = 0;
	for (int i = 1; i <= n - maxx + 1; ++i)
		for (int j = 1; j <= m - maxy + 1; ++j)
			if (C[n * m + id(i, j)] == 0)
				++ans;
	std::cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9688kb

input:

5 5 5
00000
10000
00000
00000
01001
awdsw

output:

11

result:

ok single line: '11'

Test #2:

score: 0
Accepted
time: 74ms
memory: 25512kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

77549

result:

ok single line: '77549'

Test #3:

score: 0
Accepted
time: 66ms
memory: 22580kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #4:

score: 0
Accepted
time: 72ms
memory: 22260kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #5:

score: 0
Accepted
time: 67ms
memory: 22968kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #6:

score: 0
Accepted
time: 69ms
memory: 23404kb

input:

500 500 750
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15625

result:

ok single line: '15625'

Test #7:

score: 0
Accepted
time: 378ms
memory: 70948kb

input:

1000 1000 300000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

83496

result:

ok single line: '83496'

Test #8:

score: 0
Accepted
time: 398ms
memory: 72628kb

input:

1000 1000 1000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

63001

result:

ok single line: '63001'

Test #9:

score: 0
Accepted
time: 372ms
memory: 69468kb

input:

1000 1000 1500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

62500

result:

ok single line: '62500'

Test #10:

score: 0
Accepted
time: 2267ms
memory: 266388kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #11:

score: 0
Accepted
time: 2235ms
memory: 266420kb

input:

1500 1500 5000000
100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...

output:

22801

result:

ok single line: '22801'

Test #12:

score: 0
Accepted
time: 4ms
memory: 9716kb

input:

2 2 4
00
01
dada

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 2187ms
memory: 265788kb

input:

1500 1500 5000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

141376

result:

ok single line: '141376'

Test #14:

score: 0
Accepted
time: 2050ms
memory: 251476kb

input:

1500 1500 2250
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

140625

result:

ok single line: '140625'

Test #15:

score: 0
Accepted
time: 3ms
memory: 10016kb

input:

50 60 20
000000000000000000000000010000000000000000000010000000000000
000000000000000000000000000000000000000000000000010000000000
000000000000000000000000000000000000000000010000000000001000
000000000000000000000000000000000100000000000000010000000000
00000000010000000000000000000000000000000000000...

output:

1633

result:

ok single line: '1633'

Test #16:

score: 0
Accepted
time: 2ms
memory: 9920kb

input:

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

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 69ms
memory: 26536kb

input:

500 500 500000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

15876

result:

ok single line: '15876'

Test #18:

score: 0
Accepted
time: 74ms
memory: 25024kb

input:

500 500 500
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

228475

result:

ok single line: '228475'

Test #19:

score: 0
Accepted
time: 62ms
memory: 22332kb

input:

500 500 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

53530

result:

ok single line: '53530'

Test #20:

score: 0
Accepted
time: 75ms
memory: 25292kb

input:

500 500 50000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 68ms
memory: 22140kb

input:

500 500 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

9699

result:

ok single line: '9699'