QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407044 | #8552. Sticks | SampsonYW | AC ✓ | 93ms | 47896kb | C++14 | 2.0kb | 2024-05-07 21:39:54 | 2024-05-07 21:39:54 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 3005
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
int s = 1;
while(n) {
if(n & 1) s = 1ll * s * p % P;
p = 1ll * p * p % P, n >>= 1;
}
return s;
}
il void chkmin(int &x, int y) {(x > y) && (x = y);}
int n;
string str[N];
int dp[N][N];
bool F[N]; int C[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
FOR(i, 1, n) cin >> str[i], str[i] = "1" + str[i];
dp[0][0] = 1;
FOR(i, 0, n) C[i] = 1;
FOR(i, 1, n) {
bool f = 0; int c, s = 0;
FOR(j, 0, n) {
if(str[i][j] == '0') f = 1;
if(str[i][j] == '1') {
if(f) c = 0; else c = 1;
}
if(str[i][j] == '?' && !f) ++c;
addr(dp[i][j], 1ll * c * dp[i - 1][j] % P);
if(!f) {
if(F[j]) addr(dp[i][j], 1ll * C[j] * s % P);
else addr(dp[i][j], 1ll * (C[j] - 1) * s % P);
}
s = add(1ll * s * C[j] % P, dp[i - 1][j]);
if(str[i][j] == '0') F[j] = 1;
if(str[i][j] == '1') {
if(F[j]) C[j] = 0; else C[j] = 1;
}
if(str[i][j] == '?' && !F[j]) ++C[j];
}
}
int s = 0;
FOR(j, 0, n) s = add(1ll * s * C[j] % P, dp[n][j]);
cout << s;
cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3952kb
input:
2 ?? ??
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
5 ??1?? ?1??0 ??0?? ???1? ??1??
output:
3144
result:
ok 1 number(s): "3144"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
10 0000000000 ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ??????????
output:
361458985
result:
ok 1 number(s): "361458985"
Test #4:
score: 0
Accepted
time: 62ms
memory: 47864kb
input:
3000 ??????????????????????????????????????????????????????????0?????????????????????0??????????????????????????????????????????????????????????????????????????????????????0???????????????????????????????????????????0???????????????????????????????????????????????????????????????????????????????????...
output:
56427841
result:
ok 1 number(s): "56427841"
Test #5:
score: 0
Accepted
time: 57ms
memory: 47836kb
input:
3000 ????????????????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
145247225
result:
ok 1 number(s): "145247225"
Test #6:
score: 0
Accepted
time: 57ms
memory: 47824kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
925248762
result:
ok 1 number(s): "925248762"
Test #7:
score: 0
Accepted
time: 48ms
memory: 47828kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
845505610
result:
ok 1 number(s): "845505610"
Test #8:
score: 0
Accepted
time: 68ms
memory: 47836kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
123028256
result:
ok 1 number(s): "123028256"
Test #9:
score: 0
Accepted
time: 64ms
memory: 47896kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????1???1??????????????????????????????????????????????????????????????????????1????????????????????????????????????????????????????????????????...
output:
242286033
result:
ok 1 number(s): "242286033"
Test #10:
score: 0
Accepted
time: 68ms
memory: 47880kb
input:
3000 ??????????????????????????1????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
448817936
result:
ok 1 number(s): "448817936"
Test #11:
score: 0
Accepted
time: 58ms
memory: 47860kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
621258555
result:
ok 1 number(s): "621258555"
Test #12:
score: 0
Accepted
time: 60ms
memory: 47888kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
552098298
result:
ok 1 number(s): "552098298"
Test #13:
score: 0
Accepted
time: 57ms
memory: 47884kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
190431651
result:
ok 1 number(s): "190431651"
Test #14:
score: 0
Accepted
time: 54ms
memory: 47828kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 63ms
memory: 47824kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
641634738
result:
ok 1 number(s): "641634738"
Test #16:
score: 0
Accepted
time: 75ms
memory: 47880kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
434138343
result:
ok 1 number(s): "434138343"
Test #17:
score: 0
Accepted
time: 71ms
memory: 47856kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
70334815
result:
ok 1 number(s): "70334815"
Test #18:
score: 0
Accepted
time: 74ms
memory: 47808kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
26692788
result:
ok 1 number(s): "26692788"
Test #19:
score: 0
Accepted
time: 54ms
memory: 47892kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
513359183
result:
ok 1 number(s): "513359183"
Test #20:
score: 0
Accepted
time: 60ms
memory: 47868kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
144382583
result:
ok 1 number(s): "144382583"
Test #21:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
2 10 01
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 84ms
memory: 47864kb
input:
3000 1???11111??1???1?1?1111?1111??11?11?????11?1?1?1?1?1???111???111???11?1???11?11??1?11???1??111???11??1????1??1?111??1111?1??1?1?1?1111?1??11?111?1?1??11???11?1?1111??11???????1????1???1?1??111?11?1??1111?1111?1????11?11?1??1?1???1????11?1111?1?1?1??1111???1?11?111?1????1?1?11?11???1???????111?1...
output:
354584112
result:
ok 1 number(s): "354584112"
Test #25:
score: 0
Accepted
time: 93ms
memory: 47828kb
input:
3000 111?1111??11??1?1??1???1?????111???1?11111??1?111?1??1?1????11?11111??1??1?11??11????1??11??11?1???1111???1?11?111?11?1???1?11?11?111?11??1???????1?1??11?1111??????1?1??1111????111111111???1?111??1???111???1?11??11?1??1?11??1?1?111?????1??11?1????1???11??1?11?11111?1111??1?1?1?1???1?11111?1?111...
output:
46093564
result:
ok 1 number(s): "46093564"
Test #26:
score: 0
Accepted
time: 73ms
memory: 47864kb
input:
3000 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 58ms
memory: 47892kb
input:
3000 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed