QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#778785 | #9476. 012 Grid | IllusionaryDominance# | AC ✓ | 219ms | 78676kb | C++20 | 3.0kb | 2024-11-24 16:15:38 | 2024-11-24 16:15:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 8e5 + 10;
const ll MOD = 998244353;
ll fact[N], ifact[N];
ll ksm(ll x, ll y){
ll re = 1;
for (; y; y >>= 1){
if(y & 1) re = re * x % MOD;
x = x * x % MOD;
}
return re;
}
ll C(int n, int m){if(n < 0 || m < 0 || n < m)return 0; return fact[n] * ifact[m] % MOD * ifact[n - m] % MOD;}
const long long g = 3, _g = ksm(3, MOD - 2);
int n, m;
int R[N << 2];
int limit = 1, L;
void NTT(long long *A, int op)
{
for (int i = 0; i < limit; ++ i) if(i < R[i]) swap(A[i], A[R[i]]);
for (int len = 1; len < limit; len <<= 1)
{
long long X = ksm(op == 1 ? g : _g, (MOD - 1) / (len << 1));
for (int i = 0; i < limit; i += (len << 1))
{
long long pw = 1;
for (int j = 0; j < len; ++ j)
{
long long x = A[i + j], y = pw * A[i + j + len] % MOD;
A[i + j] = (x + y) % MOD; A[i + j + len] = (x - y + MOD) % MOD;
pw = pw * X % MOD;
}
}
}
}
void mul(long long *A, long long *B, int n, int m)
{
limit = 1, L = 0;
memset(R, 0, sizeof(R));
while(limit <= n + m)limit <<= 1, ++ L;
for (int i = 0; i < limit; ++ i)R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
NTT(A, 1);
NTT(B, 1);
for (int i = 0; i < limit; ++ i)
(A[i] *= B[i]) %= MOD;
NTT(A, 0);
long long div = ksm(limit, MOD - 2);
for (int i = 0; i <= n + m; ++ i) (A[i] *= div) %= MOD;
}
long long A[N << 2], B[N << 2];
ll calc(int n, int m) {return C(n + m - 2, n - 1);}
ll Calc(int n, int m) {return (calc(n - 1, m - 1) * calc(n - 1, m - 1) % MOD - calc(n - 2, m) * calc(n, m - 2) % MOD + MOD) % MOD;}
int main() {
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
fact[0] = 1;
for (int i = 1; i < N; ++ i) fact[i] = fact[i - 1] * i % MOD;
ifact[N - 1] = ksm(fact[N - 1], MOD - 2);
for (int i = N - 2; ~i; -- i) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
int n, m;
cin >> n >> m;
ll ans = 0;
// for (int i = 0; i <= n; ++ i)
// for (int j = 0; j <= m; ++ j)
// (ans += Calc(n - i + 1, m - j + 1) * (1 + (i != 0 || j != 0))) %= MOD;
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
for (int i = 0; i <= n - 1; ++ i) A[i] = ifact[i] * ifact[i] % MOD;
for (int i = 0; i <= m - 1; ++ i) B[i] = ifact[i] * ifact[i] % MOD;
mul(A, B, n - 1, m - 1);
for (int l = 0; l <= n + m - 2; ++ l) (ans += A[l] * fact[l] % MOD * fact[l]) %= MOD;
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
for (int i = 1; i <= n - 1; ++ i) A[i] = ifact[i - 1] * ifact[i + 1] % MOD;
for (int i = 1; i <= m - 1; ++ i) B[i] = ifact[i - 1] * ifact[i + 1] % MOD;
mul(A, B, n - 1, m - 1);
for (int l = 0; l <= n + m - 2; ++ l) (ans += MOD - A[l] * fact[l] % MOD * fact[l] % MOD) %= MOD;
ans = (ans * 2 - Calc(n + 1, m + 1) + MOD) % MOD;
for (int i = 2; i <= n - 1; ++ i) (ans += Calc(i, m + 1) * (n - i)) %= MOD;
for (int i = 2; i <= m - 1; ++ i) (ans += Calc(n + 1, i) * (m - i)) %= MOD;
cout << (ans + 2) % MOD;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 17ms
memory: 78568kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 13ms
memory: 78592kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 205ms
memory: 78536kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 22ms
memory: 78592kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 18ms
memory: 78628kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 7ms
memory: 78620kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 18ms
memory: 78540kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 18ms
memory: 78600kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 14ms
memory: 78624kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 11ms
memory: 78540kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 3ms
memory: 78544kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 11ms
memory: 78576kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 17ms
memory: 78660kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 19ms
memory: 78544kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 11ms
memory: 78624kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 13ms
memory: 78600kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 23ms
memory: 78600kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 17ms
memory: 78536kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 21ms
memory: 78564kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 19ms
memory: 78536kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 22ms
memory: 78628kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 22ms
memory: 78616kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 17ms
memory: 78600kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 219ms
memory: 78592kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 95ms
memory: 78628kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 100ms
memory: 78536kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 54ms
memory: 78640kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 206ms
memory: 78568kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 100ms
memory: 78588kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 111ms
memory: 78528kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 103ms
memory: 78592kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 101ms
memory: 78576kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 103ms
memory: 78616kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 214ms
memory: 78600kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 208ms
memory: 78576kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 201ms
memory: 78592kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 3ms
memory: 78600kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 53ms
memory: 78600kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 53ms
memory: 78676kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 12ms
memory: 78536kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed