QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22588 | #2841. 赛艇 | lindongli2004# | WA | 594ms | 292764kb | C++14 | 4.4kb | 2022-03-09 23:24:59 | 2022-04-30 01:25:09 |
Judging History
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;
}
详细
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'