QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716710#8552. SticksDaiRuiChen007AC ✓104ms12804kbC++17809b2024-11-06 15:52:302024-11-06 15:52:30

Judging History

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

  • [2024-11-06 15:52:30]
  • 评测
  • 测评结果:AC
  • 用时:104ms
  • 内存:12804kb
  • [2024-11-06 15:52:30]
  • 提交

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