UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198813#2335. matrixtkswls1003097ms283000kbC++113.6kb2023-12-02 10:56:392023-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