ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198813 | #2335. matrix | tkswls | 100 | 3097ms | 283000kb | C++11 | 3.6kb | 2023-12-02 10:56:39 | 2023-12-02 12:05:13 |
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
int n, m, a[3005][3005], sum[3005][3005], h[3005][3005], l[3005][3005], ans, aa[15][15], b[15][15], cc[15][15], d[15][15];
const int mod = 998244353;
char c;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
a[i][j] = c - '0';
a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
sum[i][j] += a[i][j];
h[i][j] += a[i][j];
l[i][j] += a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mod + sum[i][j]) % mod;
h[i][j] = (h[i][j] + h[i][j - 1]) % mod;
l[i][j] = (l[i][j] + l[i - 1][j]) % mod;
}
}
int p, q, e, w;
ans = 3 * (n * (n + 1) / 2) % mod * (m * (m + 1) / 2) % mod;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans += a[i][j] * 2 * ((i * j + (n - i) * (m - j) - (i * (m - j)) - j * (n - i) + 2 * mod) % mod) % mod;
ans %= mod;
ans += (a[i][j] * a[i][j] % mod * (i) * (j) % mod - 2 * a[i][j] * ((h[i][j - 1] * i + l[i - 1][j] * j ) % mod) % mod + a[i][j] * sum[i - 1][j - 1] % mod) % mod;
ans = (ans + mod) % mod;
ans += (a[i][j] * a[i][j] % mod * (n - i) * (m - j) % mod - 2 * a[i][j] * ((h[i][m] - h[i][j] + mod) % mod * (n - i) % mod + (l[n][j] - l[i][j] + mod) % mod * (m - j)) % mod + a[i][j] * (sum[n][m] - sum[n][j] - sum[i][m] + sum[i][j] + mod) % mod + mod) % mod;
ans = (ans + mod) % mod;
ans += (a[i][j] * a[i][j] % mod * (((i * (m - j)) + j * (n - i)) % mod)) % mod;
ans += (a[i][j] * ((sum[i - 1][m] - sum[i - 1][j] + sum[n][j - 1] - sum[i][j - 1] + 2 * mod) % mod)) % mod;
ans = (ans + mod) % mod;
}
}
cout << ans;
}
//3 3
//100
//000
//000
//做过最恶心的签到题,没有之一
//除了能做出来没有其他的优点了
//可能还卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
//别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常别被卡常
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1336kb
input:
5 6 001010 101101 101000 101111 100010
output:
8633
result:
ok 1 number(s): "8633"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1744kb
input:
29 28 0000100001101111001010000100 0100010101011000110100000011 0100110111111100101001011111 1111100...
output:
987592606
result:
ok 1 number(s): "987592606"
Test #3:
score: 0
Accepted
time: 1ms
memory: 1764kb
input:
30 29 10101101111101101110010111010 10100110000101100011011001001 10010011000010000101110010000 0111...
output:
215284524
result:
ok 1 number(s): "215284524"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1732kb
input:
28 29 01011001000101110000111010110 11110000000010100111101000000 01101100110011011110001000110 1100...
output:
76459843
result:
ok 1 number(s): "76459843"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1764kb
input:
30 30 010111001111001011000111000110 100000101111111001001111110111 110101001111110010110101011010 0...
output:
617859114
result:
ok 1 number(s): "617859114"
Test #6:
score: 0
Accepted
time: 0ms
memory: 1760kb
input:
30 28 1100100100000101010101100010 0001100110100000010011011111 1111110001100000110010010101 0100110...
output:
144394367
result:
ok 1 number(s): "144394367"
Test #7:
score: 0
Accepted
time: 0ms
memory: 1760kb
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: 0ms
memory: 1340kb
input:
5 6 001000 001010 011111 100111 011011
output:
10735
result:
ok 1 number(s): "10735"
Test #9:
score: 0
Accepted
time: 2ms
memory: 2672kb
input:
77 78 101011011111001001110100000001110000001110001111011101110010010001010011001010 101111001111100...
output:
142247719
result:
ok 1 number(s): "142247719"
Test #10:
score: 0
Accepted
time: 0ms
memory: 2684kb
input:
77 80 10010000100010011110001100110000100111010000010101110111100111100011100001000000 1111110011110...
output:
319987876
result:
ok 1 number(s): "319987876"
Test #11:
score: 0
Accepted
time: 1ms
memory: 2688kb
input:
78 77 01100101000010111010000001101111000001110001010011100001000100101110100110010 1111110001101001...
output:
283388938
result:
ok 1 number(s): "283388938"
Test #12:
score: 0
Accepted
time: 0ms
memory: 2704kb
input:
79 77 10010000101010100110110101011001111001100011010000100011000100011000101001001 1110100110100000...
output:
1512427
result:
ok 1 number(s): "1512427"
Test #13:
score: 0
Accepted
time: 4ms
memory: 2672kb
input:
77 78 010111011000000110110100010101111100000110100111000011101100010010101100011111 000010110110010...
output:
661251980
result:
ok 1 number(s): "661251980"
Test #14:
score: 0
Accepted
time: 0ms
memory: 2700kb
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: 1336kb
input:
5 6 010111 110001 010010 101010 110010
output:
7313
result:
ok 1 number(s): "7313"
Test #16:
score: 0
Accepted
time: 23ms
memory: 16992kb
input:
499 498 10110001001100101101101110011011110110111101001010011101100011101101000011011101100011010010...
output:
419096472
result:
ok 1 number(s): "419096472"
Test #17:
score: 0
Accepted
time: 23ms
memory: 16960kb
input:
497 500 11101100110000011101011000011001010001001100100010010001011111010010010010101101110101111001...
output:
254869693
result:
ok 1 number(s): "254869693"
Test #18:
score: 0
Accepted
time: 15ms
memory: 16964kb
input:
498 498 01101100010001010011110110001101100100000001001010110101000101110001110010101111011111111101...
output:
533501780
result:
ok 1 number(s): "533501780"
Test #19:
score: 0
Accepted
time: 11ms
memory: 16932kb
input:
497 498 00010100101010001000100010010000100001111001011001100010000010011110010101111111101010101001...
output:
301316280
result:
ok 1 number(s): "301316280"
Test #20:
score: 0
Accepted
time: 23ms
memory: 17056kb
input:
500 500 01100001010101111010010111100101011011010010001111101001001010100000100000111011001001011110...
output:
345264499
result:
ok 1 number(s): "345264499"
Test #21:
score: 0
Accepted
time: 24ms
memory: 17028kb
input:
500 498 01010111111111010011010110101010110000010111001111101011001101001110101110100101111110000011...
output:
394599124
result:
ok 1 number(s): "394599124"
Subtask #4:
score: 40
Accepted
Test #22:
score: 40
Accepted
time: 0ms
memory: 1336kb
input:
5 6 100010 110100 110001 010101 001000
output:
6067
result:
ok 1 number(s): "6067"
Test #23:
score: 0
Accepted
time: 485ms
memory: 282808kb
input:
2998 2997 010010011011100101101110101110110001111010011101010010010011001100000001100011010010011000...
output:
870886001
result:
ok 1 number(s): "870886001"
Test #24:
score: 0
Accepted
time: 503ms
memory: 282712kb
input:
2997 2999 000001000001111111000010100011111001010111011011111001011011000010001111101101110000101101...
output:
327694031
result:
ok 1 number(s): "327694031"
Test #25:
score: 0
Accepted
time: 513ms
memory: 283000kb
input:
3000 2999 011011110101101110100011001100101011001010110100000011011101101001010110111010100000111111...
output:
741117474
result:
ok 1 number(s): "741117474"
Test #26:
score: 0
Accepted
time: 500ms
memory: 282808kb
input:
2998 3000 011011100101010000011001100011001001110011011000000101111100100011100001000000110000100001...
output:
784651777
result:
ok 1 number(s): "784651777"
Test #27:
score: 0
Accepted
time: 495ms
memory: 283000kb
input:
3000 2997 101001100111011110010000011001001001010111101001001001100001111010010111101111111001100111...
output:
282838940
result:
ok 1 number(s): "282838940"
Test #28:
score: 0
Accepted
time: 474ms
memory: 282904kb
input:
2999 2997 110000110000000101101010111010110101101001000000101001100001111110101111011110001001011101...
output:
387738552
result:
ok 1 number(s): "387738552"
Extra Test:
score: 0
Extra Test Passed