QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657423 | #9476. 012 Grid | open your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)# | AC ✓ | 81ms | 20108kb | C++14 | 3.8kb | 2024-10-19 14:44:13 | 2024-10-19 14:44:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, o = 19, len = 1 << o;
int n, m, fac[len], ifac[len];
int f[len], g[len];
int power(int a, int n) {
int tp = 1;
while (n) {
if (n & 1) {
tp = 1ll * tp * a % mod;
}
a = 1ll * a * a % mod, n >>= 1;
}
return tp;
}
int c(int n, int m) { return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
void prep(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = 1ll * fac[i - 1] * i % mod;
}
ifac[n] = power(fac[n], mod - 2);
for (int i = n - 1; i != -1; i--) {
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}
}
namespace poly {
using u64 = unsigned long long;
int r[len], w[len], up, l;
void init() {
int w1 = power(3, (mod - 1) >> o);
w[len >> 1] = 1;
for (int i = (len >> 1) + 1; i != len; i++) {
w[i] = 1ll * w[i - 1] * w1 % mod;
}
for (int i = (len >> 1) -1; i; i--) {
w[i] = w[i << 1];
}
for (int i = 0; i != len; i++) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (o - 1));
}
}
void ntt(int *a, int n, bool op) {
static u64 t[len];
for (int i = 0; i != n; i += 2) {
int x = a[r[i] >> (o - l)], y = a[r[i + 1] >> (o - l)];
t[i] = x + y, t[i + 1] = x + mod - y;
}
for (int l = 2; l != n; l <<= 1) {
int *k = w + l;
if (l == 1 << 18) {
for (u64 *f = t; f != t + n; f++) {
*f %= mod;
}
}
for (u64 *f = t; f != t + n; f += l) {
for (int *j = k; j != k + l; j++, f++) {
u64 x = *f, y = f[l] * *j % mod;
f[l] = x + mod - y, *f += y;
}
}
}
if (op) {
for (int i = 0, x = mod - (mod >> l); i != n; i++) {
a[i] = t[i] % mod * x % mod;
}
reverse(a + 1, a + n);
} else {
for (int i = 0; i != n; i++) {
a[i] = t[i] % mod;
}
}
}
int pre(int n) {
l = __lg(n) + 1;
return up = 1 << l;
}
}
int main(){
cin >> n >> m;
prep(n + m);
poly::init();
for (int i = 0; i != n; i++) {
f[i] = 1ll * ifac[i] * ifac[i] % mod;
}
for (int i = 0; i != m; i++) {
g[i] = 1ll * ifac[i] * ifac[i] % mod;
}
int up = poly::pre(n + m);
poly::ntt(f, up, 0), poly::ntt(g, up, 0);
for (int i = 0; i != up; i++) {
f[i] = 1ll * f[i] * g[i] % mod;
}
poly::ntt(f, up, 1);
int ans = 1;
for (int i = 0; i <= n + m; i++) {
ans = (ans + 1ll * f[i] * fac[i] % mod * fac[i]) % mod;
}
memset(f, 0, sizeof f), memset(g, 0, sizeof g);
for (int i = 1; i != n; i++) {
f[i] = 1ll * ifac[i - 1] * ifac[i + 1] % mod;
}
for (int j = 1; j != m; j++) {
g[j] = 1ll * ifac[j - 1] * ifac[j + 1] % mod;
}
poly::ntt(f, up, 0), poly::ntt(g, up, 0);
for (int i = 0; i != up; i++) {
f[i] = 1ll * f[i] * g[i] % mod;
}
poly::ntt(f, up, 1);
for (int i = 0; i <= n + m; i++) {
ans = (ans + 1ll * (mod - f[i]) * fac[i] % mod * fac[i]) % mod;
}
ans = 2 * ans % mod;
ans = (ans + 1ll * (mod - c(n + m - 2, n - 1)) * c(n + m - 2, n - 1) + 1ll * c(n + m - 2, n - 2) * c(n + m - 2, n)) % mod;
for (int l = 0; l < m - 2; l++) {
int v = (1ll * c(l + n - 1, n - 1) * c(l + n - 1, n - 1) + 1ll * (mod - c(l + n - 1, n)) * c(l + n - 1, n - 2)) % mod;
ans = (ans + 1ll * (m - 2 - l) * v) % mod;
}
for (int l = 0; l < n - 2; l++) {
int v = (1ll * c(l + m - 1, m - 1) * c(l + m - 1, m - 1) + 1ll * (mod - c(l + m - 1, m)) * c(l + m - 1, m - 2)) % mod;
ans = (ans + 1ll * (n - 2 - l) * v) % mod;
}
cout << ans << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 16572kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 0ms
memory: 16808kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 71ms
memory: 20084kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 4ms
memory: 16616kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 4ms
memory: 16200kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 0ms
memory: 16876kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 0ms
memory: 17004kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 0ms
memory: 16388kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 0ms
memory: 16484kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 0ms
memory: 17704kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 2ms
memory: 17744kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 2ms
memory: 17560kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 0ms
memory: 16524kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 3ms
memory: 16428kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 0ms
memory: 16900kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 6ms
memory: 16580kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 5ms
memory: 17648kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 3ms
memory: 16748kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 2ms
memory: 16948kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 6ms
memory: 17200kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 6ms
memory: 16516kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 3ms
memory: 16140kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 3ms
memory: 16816kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 67ms
memory: 20088kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 30ms
memory: 19280kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 33ms
memory: 19500kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 12ms
memory: 17620kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 71ms
memory: 20020kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 35ms
memory: 18748kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 30ms
memory: 19804kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 30ms
memory: 19544kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 29ms
memory: 19424kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 27ms
memory: 18896kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 79ms
memory: 20108kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 73ms
memory: 20084kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 81ms
memory: 20040kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 0ms
memory: 16668kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 12ms
memory: 18108kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 12ms
memory: 17836kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 0ms
memory: 16396kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed