QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657423#9476. 012 Gridopen your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)#AC ✓81ms20108kbC++143.8kb2024-10-19 14:44:132024-10-19 14:44:21

Judging History

This is the latest submission verdict.

  • [2024-10-19 14:44:21]
  • Judged
  • Verdict: AC
  • Time: 81ms
  • Memory: 20108kb
  • [2024-10-19 14:44:13]
  • Submitted

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