QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#658917 | #9476. 012 Grid | ucup-team4474# | AC ✓ | 149ms | 19192kb | C++20 | 5.3kb | 2024-10-19 17:56:05 | 2024-10-19 17:56:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 4e5 + 5;
int fac[N], ifac[N];
int inv(int x)
{
int res = 1, y = mod - 2;
while (y)
{
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
int binom(int x, int y)
{
if (x < 0 or y < 0 or x < y) return 0;
return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int cal(int x, int y)
{
int ret = 1ll * binom(x + y - 2, x - 1) * binom(x + y - 2, y - 1) % mod;
ret = (ret + mod - 1ll * binom(x + y - 2, x - 2) * binom(x + y - 2, y - 2) % mod) % mod;
return ret;
}
const int P = 998244353;
using i64 = long long;
using Poly = vector<int>;
#define MUL(a, b) (i64(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0)
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P : 0)
Poly getInv(int L)
{
Poly inv(L);
inv[1] = 1;
for (int i = 2; i < L; i++)
inv[i] = MUL((P - P / i), inv[P % i]);
return inv;
}
int POW(i64 a, int b = P - 2, i64 x = 1)
{
for (; b; b >>= 1, a = a * a % P)
if (b & 1)
x = x * a % P;
return x;
}
namespace NTT
{
const int g = 3;
Poly Omega(int L)
{
int wn = POW(g, P / L);
Poly w(L);
w[L >> 1] = 1;
for (int i = L / 2 + 1; i < L; i++)
w[i] = MUL(w[i - 1], wn);
for (int i = L / 2 - 1; i >= 1; i--)
w[i] = w[i << 1];
return w;
}
auto W = Omega(1 << 20);
void DIF(int *a, int n)
{
for (int k = n >> 1; k; k >>= 1)
for (int i = 0, y; i < n; i += k << 1)
for (int j = 0; j < k; j++)
y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
}
void IDFT(int *a, int n)
{
for (int k = 1; k < n; k <<= 1)
for (int i = 0, x, y; i < n; i += k << 1)
for (int j = 0; j < k; j++)
x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
int Inv = P - (P - 1) / n;
for (int i = 0; i < n; i++)
a[i] = MUL(a[i], Inv);
reverse(a + 1, a + n);
}
}
namespace Polynomial
{
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
void norm(Poly &a)
{
if (!a.empty())
a.resize(norm(a.size()), 0);
else
a = {0};
}
void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
void IDFT(Poly &a) { NTT::IDFT(a.data(), a.size()); }
Poly &dot(Poly &a, Poly &b)
{
for (int i = 0; i < a.size(); i++)
a[i] = MUL(a[i], b[i]);
return a;
}
Poly operator*(Poly a, Poly b)
{
int n = a.size() + b.size() - 1, L = norm(n);
if (a.size() <= 8 || b.size() <= 8)
{
Poly c(n);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] = (c[i + j] + (i64)a[i] * b[j] % P) % P;
return c;
}
a.resize(L), b.resize(L);
DFT(a), DFT(b), dot(a, b), IDFT(a);
return a.resize(n), a;
}
}
using namespace Polynomial;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
fac[0] = 1;
for (int i = 1; i <= 400000; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[400000] = inv(fac[400000]);
for (int i = 399999; i >= 0; i--)
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
int n, m;
cin >> n >> m;
int ans = 2;
for (int i = 1; i <= n; i++) ans = (ans + 1ll * (n - i + 1) * cal(i, m) % mod) % mod;
for (int i = 1; i < m; i++) ans = (ans + 1ll * (m - i) * cal(n, i) % mod) % mod;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j < m; j++) ans = (ans + cal(i, j)) % mod;
// }
// for (int i = 1; i < m; i++)
// {
// for (int j = 1; j < n; j++) ans = (ans + cal(j, i)) % mod;
// }
{
Poly f(n + 1), g(m);
for (int i = 1; i <= n; i++) f[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
for (int i = 1; i < m; i++) g[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
auto h = f * g;
int tmp = 0;
for (int i = 2; i <= n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
ans = (ans + tmp) % mod;
f.assign(n + 1, 0);
g.assign(m, 0);
for (int i = 2; i <= n; i++) f[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
for (int i = 2; i < m; i++) g[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
h = f * g;
tmp = 0;
for (int i = 2; i <= n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
ans = (ans + mod - tmp) % mod;
}
{
Poly f(n), g(m);
for (int i = 1; i < n; i++) f[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
for (int i = 1; i < m; i++) g[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
auto h = f * g;
int tmp = 0;
for (int i = 2; i < n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
ans = (ans + tmp) % mod;
f.assign(n, 0);
g.assign(m, 0);
for (int i = 2; i < n; i++) f[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
for (int i = 2; i < m; i++) g[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
h = f * g;
tmp = 0;
for (int i = 2; i < n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
ans = (ans + mod - tmp) % mod;
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 10352kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 8ms
memory: 10420kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 141ms
memory: 19192kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 8ms
memory: 10412kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 8ms
memory: 10340kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 8ms
memory: 10336kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 8ms
memory: 10368kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 4ms
memory: 10212kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 8ms
memory: 10228kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 5ms
memory: 10480kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 4ms
memory: 10112kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 8ms
memory: 10152kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 8ms
memory: 10296kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 8ms
memory: 10760kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 7ms
memory: 10664kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 7ms
memory: 10668kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 11ms
memory: 10636kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 11ms
memory: 10776kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 11ms
memory: 10692kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 9ms
memory: 10768kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 7ms
memory: 10748kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 11ms
memory: 10760kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 7ms
memory: 10748kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 146ms
memory: 18604kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 64ms
memory: 14448kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 70ms
memory: 14024kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 43ms
memory: 12416kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 138ms
memory: 18676kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 78ms
memory: 15052kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 75ms
memory: 14508kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 63ms
memory: 14068kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 71ms
memory: 14112kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 73ms
memory: 14812kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 149ms
memory: 19156kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 137ms
memory: 19172kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 137ms
memory: 19164kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 8ms
memory: 10204kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 9ms
memory: 11948kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 11ms
memory: 11848kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 5ms
memory: 10440kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed