UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198809#2335. matrixEaoci1001518ms143904kbC++111006b2023-12-02 10:39:242023-12-02 12:04:45

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int reac(){
	char ch=getchar();
	while(ch!='0'&&ch!='1')ch=getchar();
	return ch-'0';
}
const int N=3030,mod=998244353;
int n,m,f[N][N],g[N][N],ans;
signed main(){
	n=read(),m=read(),ans=n*(n+1)*m*(m+1)/4*3%mod;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=reac();
			g[i][j]=(g[i][j-1]+g[i-1][j]-g[i-1][j-1]+mod)%mod;
			if(f[i][j]){
				g[i][j]=(g[i][j]+i*j)%mod;
				ans=(ans+(2*g[i][j]+i*j)*(n-i+1)*(m-j+1))%mod;
			}
		}
	}
	memset(g,0,sizeof(g));
	for(int i=1;i<=n;i++){
		for(int j=m;j;j--){
			g[i][j]=(g[i][j+1]+g[i-1][j]-g[i-1][j+1]+mod)%mod;
			if(f[i][j]){
				g[i][j]=(g[i][j]+i*(m-j+1))%mod;
				ans=(ans+2*g[i-1][j+1]*(n-i+1)*j)%mod;
			}
		}
	}
	cout<<ans;
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 4ms
memory: 72908kb

input:

5 6
001010
101101
101000
101111
100010

output:

8633

result:

ok 1 number(s): "8633"

Test #2:

score: 0
Accepted
time: 4ms
memory: 73008kb

input:

29 28
0000100001101111001010000100
0100010101011000110100000011
0100110111111100101001011111
1111100...

output:

987592606

result:

ok 1 number(s): "987592606"

Test #3:

score: 0
Accepted
time: 3ms
memory: 73012kb

input:

30 29
10101101111101101110010111010
10100110000101100011011001001
10010011000010000101110010000
0111...

output:

215284524

result:

ok 1 number(s): "215284524"

Test #4:

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

input:

28 29
01011001000101110000111010110
11110000000010100111101000000
01101100110011011110001000110
1100...

output:

76459843

result:

ok 1 number(s): "76459843"

Test #5:

score: 0
Accepted
time: 7ms
memory: 73008kb

input:

30 30
010111001111001011000111000110
100000101111111001001111110111
110101001111110010110101011010
0...

output:

617859114

result:

ok 1 number(s): "617859114"

Test #6:

score: 0
Accepted
time: 7ms
memory: 73008kb

input:

30 28
1100100100000101010101100010
0001100110100000010011011111
1111110001100000110010010101
0100110...

output:

144394367

result:

ok 1 number(s): "144394367"

Test #7:

score: 0
Accepted
time: 3ms
memory: 73008kb

input:

30 30
010010110111010111001100111000
010111101110001000110011010100
110011011111110010110001001110
0...

output:

514057584

result:

ok 1 number(s): "514057584"

Subtask #2:

score: 20
Accepted

Test #8:

score: 20
Accepted
time: 4ms
memory: 72904kb

input:

5 6
001000
001010
011111
100111
011011

output:

10735

result:

ok 1 number(s): "10735"

Test #9:

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

input:

77 78
101011011111001001110100000001110000001110001111011101110010010001010011001010
101111001111100...

output:

142247719

result:

ok 1 number(s): "142247719"

Test #10:

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

input:

77 80
10010000100010011110001100110000100111010000010101110111100111100011100001000000
1111110011110...

output:

319987876

result:

ok 1 number(s): "319987876"

Test #11:

score: 0
Accepted
time: 8ms
memory: 73244kb

input:

78 77
01100101000010111010000001101111000001110001010011100001000100101110100110010
1111110001101001...

output:

283388938

result:

ok 1 number(s): "283388938"

Test #12:

score: 0
Accepted
time: 7ms
memory: 73248kb

input:

79 77
10010000101010100110110101011001111001100011010000100011000100011000101001001
1110100110100000...

output:

1512427

result:

ok 1 number(s): "1512427"

Test #13:

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

input:

77 78
010111011000000110110100010101111100000110100111000011101100010010101100011111
000010110110010...

output:

661251980

result:

ok 1 number(s): "661251980"

Test #14:

score: 0
Accepted
time: 7ms
memory: 73244kb

input:

78 80
01001111100000110100110100000110011111101101110001110101001101111000100001101010
1100011101011...

output:

183864009

result:

ok 1 number(s): "183864009"

Subtask #3:

score: 20
Accepted

Test #15:

score: 20
Accepted
time: 0ms
memory: 72908kb

input:

5 6
010111
110001
010010
101010
110010

output:

7313

result:

ok 1 number(s): "7313"

Test #16:

score: 0
Accepted
time: 19ms
memory: 76824kb

input:

499 498
10110001001100101101101110011011110110111101001010011101100011101101000011011101100011010010...

output:

419096472

result:

ok 1 number(s): "419096472"

Test #17:

score: 0
Accepted
time: 11ms
memory: 76816kb

input:

497 500
11101100110000011101011000011001010001001100100010010001011111010010010010101101110101111001...

output:

254869693

result:

ok 1 number(s): "254869693"

Test #18:

score: 0
Accepted
time: 8ms
memory: 76816kb

input:

498 498
01101100010001010011110110001101100100000001001010110101000101110001110010101111011111111101...

output:

533501780

result:

ok 1 number(s): "533501780"

Test #19:

score: 0
Accepted
time: 7ms
memory: 76804kb

input:

497 498
00010100101010001000100010010000100001111001011001100010000010011110010101111111101010101001...

output:

301316280

result:

ok 1 number(s): "301316280"

Test #20:

score: 0
Accepted
time: 16ms
memory: 76836kb

input:

500 500
01100001010101111010010111100101011011010010001111101001001010100000100000111011001001011110...

output:

345264499

result:

ok 1 number(s): "345264499"

Test #21:

score: 0
Accepted
time: 12ms
memory: 76832kb

input:

500 498
01010111111111010011010110101010110000010111001111101011001101001110101110100101111110000011...

output:

394599124

result:

ok 1 number(s): "394599124"

Subtask #4:

score: 40
Accepted

Test #22:

score: 40
Accepted
time: 7ms
memory: 72904kb

input:

5 6
100010
110100
110001
010101
001000

output:

6067

result:

ok 1 number(s): "6067"

Test #23:

score: 0
Accepted
time: 225ms
memory: 143856kb

input:

2998 2997
010010011011100101101110101110110001111010011101010010010011001100000001100011010010011000...

output:

870886001

result:

ok 1 number(s): "870886001"

Test #24:

score: 0
Accepted
time: 237ms
memory: 143832kb

input:

2997 2999
000001000001111111000010100011111001010111011011111001011011000010001111101101110000101101...

output:

327694031

result:

ok 1 number(s): "327694031"

Test #25:

score: 0
Accepted
time: 223ms
memory: 143904kb

input:

3000 2999
011011110101101110100011001100101011001010110100000011011101101001010110111010100000111111...

output:

741117474

result:

ok 1 number(s): "741117474"

Test #26:

score: 0
Accepted
time: 245ms
memory: 143856kb

input:

2998 3000
011011100101010000011001100011001001110011011000000101111100100011100001000000110000100001...

output:

784651777

result:

ok 1 number(s): "784651777"

Test #27:

score: 0
Accepted
time: 250ms
memory: 143904kb

input:

3000 2997
101001100111011110010000011001001001010111101001001001100001111010010111101111111001100111...

output:

282838940

result:

ok 1 number(s): "282838940"

Test #28:

score: 0
Accepted
time: 204ms
memory: 143880kb

input:

2999 2997
110000110000000101101010111010110101101001000000101001100001111110101111011110001001011101...

output:

387738552

result:

ok 1 number(s): "387738552"

Extra Test:

score: 0
Extra Test Passed