ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198809 | #2335. matrix | Eaoci | 100 | 1518ms | 143904kb | C++11 | 1006b | 2023-12-02 10:39:24 | 2023-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