QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22583 | #2841. 赛艇 | blackswallow# | AC ✓ | 1824ms | 227896kb | C++20 | 4.5kb | 2022-03-09 22:06:58 | 2022-04-30 01:24:24 |
Judging History
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'