QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400437#8552. Sticksgrass8cowAC ✓127ms12804kbC++17802b2024-04-27 11:41:022024-04-27 11:41:02

Judging History

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

  • [2024-04-27 11:41:02]
  • 评测
  • 测评结果:AC
  • 用时:127ms
  • 内存:12804kb
  • [2024-04-27 11:41:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,f[3010],dp[3010];
bool ex[3010];
char c[3010][3010];
const int mod=998244353;
void ad(int &x,int y){(x+=y)%=mod;}
int main(){
	scanf("%d",&n);
	f[0]=1;
	for(int i=1;i<=n;i++)scanf("%s",c[i]+1),c[0][i]=c[i][0]='1',f[i]=1;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		int s=0,z=1;bool p=0;
		for(int j=0;j<=n;j++){
			if(c[i][j]=='0')p=1;else if(c[i][j]=='1')z=!p;else if(!p)z++;
			int Z=0;
			ad(Z,1ll*dp[j]*z%mod);
			if(!p)ad(Z,1ll*(f[j]-(!ex[j]))*s%mod);
			s=1ll*s*f[j]%mod,ad(s,dp[j]);
			dp[j]=Z;
		}
		for(int j=1;j<=n;j++){
			if(c[i][j]=='0')ex[j]=1;
			else if(c[i][j]=='1')f[j]=!ex[j];
			else if(!ex[j])f[j]++;
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++)ans=1ll*ans*f[i]%mod,ad(ans,dp[i]);
	return printf("%d",ans),0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3912kb

input:

2
??
??

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

5
??1??
?1??0
??0??
???1?
??1??

output:

3144

result:

ok 1 number(s): "3144"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

10
0000000000
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????

output:

361458985

result:

ok 1 number(s): "361458985"

Test #4:

score: 0
Accepted
time: 93ms
memory: 12764kb

input:

3000
??????????????????????????????????????????????????????????0?????????????????????0??????????????????????????????????????????????????????????????????????????????????????0???????????????????????????????????????????0???????????????????????????????????????????????????????????????????????????????????...

output:

56427841

result:

ok 1 number(s): "56427841"

Test #5:

score: 0
Accepted
time: 91ms
memory: 12744kb

input:

3000
????????????????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

145247225

result:

ok 1 number(s): "145247225"

Test #6:

score: 0
Accepted
time: 86ms
memory: 12760kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

925248762

result:

ok 1 number(s): "925248762"

Test #7:

score: 0
Accepted
time: 94ms
memory: 12800kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

845505610

result:

ok 1 number(s): "845505610"

Test #8:

score: 0
Accepted
time: 87ms
memory: 12556kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

123028256

result:

ok 1 number(s): "123028256"

Test #9:

score: 0
Accepted
time: 95ms
memory: 12668kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????1???1??????????????????????????????????????????????????????????????????????1????????????????????????????????????????????????????????????????...

output:

242286033

result:

ok 1 number(s): "242286033"

Test #10:

score: 0
Accepted
time: 93ms
memory: 12760kb

input:

3000
??????????????????????????1????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

448817936

result:

ok 1 number(s): "448817936"

Test #11:

score: 0
Accepted
time: 90ms
memory: 12760kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

621258555

result:

ok 1 number(s): "621258555"

Test #12:

score: 0
Accepted
time: 93ms
memory: 12556kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

552098298

result:

ok 1 number(s): "552098298"

Test #13:

score: 0
Accepted
time: 98ms
memory: 12700kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

190431651

result:

ok 1 number(s): "190431651"

Test #14:

score: 0
Accepted
time: 94ms
memory: 12744kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 98ms
memory: 12764kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

641634738

result:

ok 1 number(s): "641634738"

Test #16:

score: 0
Accepted
time: 95ms
memory: 12800kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

434138343

result:

ok 1 number(s): "434138343"

Test #17:

score: 0
Accepted
time: 98ms
memory: 12804kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

70334815

result:

ok 1 number(s): "70334815"

Test #18:

score: 0
Accepted
time: 93ms
memory: 12684kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

26692788

result:

ok 1 number(s): "26692788"

Test #19:

score: 0
Accepted
time: 94ms
memory: 12756kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

513359183

result:

ok 1 number(s): "513359183"

Test #20:

score: 0
Accepted
time: 93ms
memory: 12760kb

input:

3000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

144382583

result:

ok 1 number(s): "144382583"

Test #21:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

1
0

output:

1

result:

ok 1 number(s): "1"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

2
10
01

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 127ms
memory: 12768kb

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: 122ms
memory: 12760kb

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: 88ms
memory: 12688kb

input:

3000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #27:

score: 0
Accepted
time: 91ms
memory: 12700kb

input:

3000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Extra Test:

score: 0
Extra Test Passed