QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716710 | #8552. Sticks | DaiRuiChen007 | AC ✓ | 104ms | 12804kb | C++17 | 809b | 2024-11-06 15:52:30 | 2024-11-06 15:52:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3005,MOD=998244353;
char s[MAXN][MAXN];
ll f[MAXN],vc[MAXN];
bool okc[MAXN];
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%s",s[i]+1),s[i][0]=s[0][i]='1',vc[i]=okc[i]=1;
f[0]=vc[0]=okc[0]=1;
for(int i=1;i<=n;++i){
ll sf=0,vr=0;
bool okr=1;
for(int j=0;j<=n;++j) {
if(s[i][j]=='0') okr=0;
else if(s[i][j]=='1') vr=okr;
else vr+=okr;
ll w=f[j]*vr%MOD;
if(okr) w=(w+sf*(vc[j]-okc[j]))%MOD;
sf=(sf*vc[j]+f[j])%MOD,f[j]=w;
}
for(int j=0;j<=n;++j) {
if(s[i][j]=='0') okc[j]=0;
else if(s[i][j]=='1') vc[j]=okc[j];
else vc[j]+=okc[j];
}
}
ll ans=0;
for(int j=0;j<=n;++j) ans=(ans*vc[j]+f[j])%MOD;
printf("%lld\n",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
input:
2 ?? ??
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
5 ??1?? ?1??0 ??0?? ???1? ??1??
output:
3144
result:
ok 1 number(s): "3144"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
10 0000000000 ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ?????????? ??????????
output:
361458985
result:
ok 1 number(s): "361458985"
Test #4:
score: 0
Accepted
time: 57ms
memory: 12724kb
input:
3000 ??????????????????????????????????????????????????????????0?????????????????????0??????????????????????????????????????????????????????????????????????????????????????0???????????????????????????????????????????0???????????????????????????????????????????????????????????????????????????????????...
output:
56427841
result:
ok 1 number(s): "56427841"
Test #5:
score: 0
Accepted
time: 63ms
memory: 12640kb
input:
3000 ????????????????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
145247225
result:
ok 1 number(s): "145247225"
Test #6:
score: 0
Accepted
time: 61ms
memory: 12724kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
925248762
result:
ok 1 number(s): "925248762"
Test #7:
score: 0
Accepted
time: 66ms
memory: 12648kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
845505610
result:
ok 1 number(s): "845505610"
Test #8:
score: 0
Accepted
time: 68ms
memory: 12732kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
123028256
result:
ok 1 number(s): "123028256"
Test #9:
score: 0
Accepted
time: 59ms
memory: 12804kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????1???1??????????????????????????????????????????????????????????????????????1????????????????????????????????????????????????????????????????...
output:
242286033
result:
ok 1 number(s): "242286033"
Test #10:
score: 0
Accepted
time: 67ms
memory: 12604kb
input:
3000 ??????????????????????????1????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
448817936
result:
ok 1 number(s): "448817936"
Test #11:
score: 0
Accepted
time: 68ms
memory: 12796kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
621258555
result:
ok 1 number(s): "621258555"
Test #12:
score: 0
Accepted
time: 67ms
memory: 12796kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
552098298
result:
ok 1 number(s): "552098298"
Test #13:
score: 0
Accepted
time: 67ms
memory: 12736kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
190431651
result:
ok 1 number(s): "190431651"
Test #14:
score: 0
Accepted
time: 58ms
memory: 12740kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 63ms
memory: 12736kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
641634738
result:
ok 1 number(s): "641634738"
Test #16:
score: 0
Accepted
time: 67ms
memory: 12724kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
434138343
result:
ok 1 number(s): "434138343"
Test #17:
score: 0
Accepted
time: 63ms
memory: 12608kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
70334815
result:
ok 1 number(s): "70334815"
Test #18:
score: 0
Accepted
time: 67ms
memory: 12712kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
26692788
result:
ok 1 number(s): "26692788"
Test #19:
score: 0
Accepted
time: 66ms
memory: 12800kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
513359183
result:
ok 1 number(s): "513359183"
Test #20:
score: 0
Accepted
time: 66ms
memory: 12652kb
input:
3000 ???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
144382583
result:
ok 1 number(s): "144382583"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
2 10 01
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 91ms
memory: 12736kb
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: 104ms
memory: 12712kb
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: 65ms
memory: 12728kb
input:
3000 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 58ms
memory: 12640kb
input:
3000 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed