QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122947#1816. Multiple ParenthesesScarlett_boyAC ✓1012ms97820kbC++179.4kb2023-07-11 15:36:402023-07-11 15:36:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 15:36:41]
  • 评测
  • 测评结果:AC
  • 用时:1012ms
  • 内存:97820kb
  • [2023-07-11 15:36:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const int mod = 998244353;
//#define int long long


int powmod(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        b >>= 1;
        a = 1ll * a * a % mod;
    }
    return res;
}


struct Combinatorial_mathematics {
    vector<int> fac, inv;

    inline int add(int &x, int y) { return x + y >= mod ? x + y - mod : x + y; }

    inline int sub(int &x, int y) { return x - y < 0 ? x - y + mod : x - y; }

    inline int mul(int &x, int y) { return 1ull * x * y % mod; }

    inline int powmod(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) res = mul(res, a);
            b >>= 1;
            a = mul(a, a);
        }
        return res;
    }

    inline int Inv(int x) { return powmod(x, mod - 2); }

    Combinatorial_mathematics(int m = 0) : fac(m + 1), inv(m + 1) {
        fac[0] = 1;
        for (int i = 1; i <= m; i++) fac[i] = mul(fac[i - 1], i);
        inv[m] = Inv(fac[m]);
        for (int i = m; i >= 1; i--) inv[i - 1] = mul(inv[i], i);
    }

    inline int C(int n, int m) {
        if (n < m || n < 0 || m < 0) return 0;
        return mul(fac[n], mul(inv[m], inv[n - m]));
    }
};


#define maxn 4000005
#define mod 998244353
#define LL long long

void Inc(int &x, int y) {
    x += y;
    (x >= mod) && (x -= mod);
}

int sub(int x, int y) {
    x -= y;
    (x < 0) && (x += mod);
    return x;
}

inline int Pow(int b, int k, int r = 1) {
    for (; k; k >>= 1, b = 1ll * b * b % mod) if (k & 1) r = 1ll * r * b % mod;
    return r;
}

namespace Math {
    LL w;
    struct N {
        LL a, b;
    };

    N operator*(const N &x, const N &y) { return (N) {(x.a * y.a + w * x.b % mod * y.b) % mod, (x.a * y.b + y.a * x.b) % mod}; }

    inline LL power(N n, LL x) {
        N res = (N) {1, 0};
        for (; x; n = n * n, x >>= 1) if (x & 1) res = res * n;
        return res.a;
    }

    inline bool check(LL x) { return power((N) {x, 0}, (mod - 1) >> 1) == 1; }

    inline int work(LL n) {
        mt19937 rnd(time(0));
        if (n == 0) return 0;
        LL a = rnd() % mod;
        while (!a || check((a * a + mod - n) % mod)) a = rnd() % mod;
        w = (a * a + mod - n) % mod;
        int ans = power((N) {a, 1}, (mod + 1) >> 1);
        return min(ans, mod - ans);
    }
}
#define inv2 499122177
#define I 86583718
int Wl, Wl2, w[maxn], lg[maxn], inv[maxn];

inline void init(int n) {
    for (Wl = 1; n >= Wl << 1; Wl <<= 1);
    int pw = Pow(3, (mod - 1) / (Wl2 = Wl << 1));
    w[Wl] = inv[0] = inv[1] = 1;
    for (int i = Wl + 1; i <= Wl2; i++) w[i] = w[i - 1] * 1ll * pw % mod;
    for (int i = Wl - 1; i >= 1; i--) w[i] = w[i << 1];
    for (int i = 2; i <= Wl2; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod, lg[i] = lg[i >> 1] + 1;
}

inline int upd(int x) { return x += x >> 31 & mod; }

inline void NTT(int *A, int n, int tp) {
    static int r[maxn] = {};
    static unsigned LL ar[maxn] = {};
    if (tp ^ 1) reverse(A + 1, A + n);
    for (int i = 0; i < n; i++) r[i] = (r[i >> 1] >> 1 | (i & 1) << lg[n] - 1), ar[i] = upd(A[r[i]]);
    for (int L = 1; L < n; L <<= 1)
        for (int s = 0, L2 = L << 1; s < n; s += L2)
            for (int k = s, x = L, t; x < L2; x++, k++) t = ar[k + L] * w[x] % mod, ar[k + L] = ar[k] - t + mod, ar[k] += t;
    for (int i = 0; i < n; i++) A[i] = ar[i] % mod;
    if (tp ^ 1) for (int i = 0; i < n; i++) A[i] = 1ll * A[i] * inv[n] % mod;
}

#define Poly vector<int>

inline Poly Sub(Poly A, Poly B) {
    if (A.size() < B.size()) A.resize(B.size()); else if (A.size() > B.size()) B.resize(A.size());
    Poly C;
    C.resize(A.size());
    for (int i = 0; i < (int) A.size(); i++) C[i] = sub(A[i], B[i]);
    return C;
}

inline Poly Der(Poly A) {
    int n = A.size();
    for (int i = 1; i < n; i++) A[i - 1] = 1ll * i * A[i] % mod;
    A[n - 1] = 0;
    return A;
}

inline Poly Int(Poly A) {
    int n = A.size();
    for (int i = n - 1; i > 0; i--) A[i] = 1ll * A[i - 1] * inv[i] % mod;
    A[0] = 0;
    return A;
}

namespace SemiConvol {
    Poly p[5][16], A;

    void ln(Poly &res, int l, int r, int n, int dep = 0) {
        if (r - l <= 256) {
            r = min(r, n);
            for (int i = l; i < r; ++i) {
                if (i == 0) res[i] = 0; else res[i] = sub(A[i], 1ll * inv[i] * res[i] % mod);
                for (int j = i + 1; j < r; ++j) res[j] = (res[j] + 1ll * res[i] * A[j - i] % mod * i) % mod;
            }
            return;
        }
        int sz = r - l >> 4;
        vector<LL> w[16];
        Poly T(sz * 2);
        int lim = 0;
        for (; lim < 16; lim++) {
            if (l + lim * sz >= n) break;
            w[lim].resize(sz << 1);
        }
        for (int i = 0; i < lim; i++) {
            if (i) {
                for (int j = 0; j < sz * 2; j++) T[j] = w[i][j] % mod;
                NTT(T.data(), sz * 2, -1);
                for (int j = 0; j < sz; j++) Inc(res[l + i * sz + j], T[sz + j]);
            }
            ln(res, l + i * sz, l + (i + 1) * sz, n, dep + 1);
            if (i < lim - 1) {
                for (int j = 0; j < sz; j++) T[j + sz] = 0, T[j] = 1ll * res[l + i * sz + j] * (l + i * sz + j) % mod;
                NTT(T.data(), sz << 1, 1);
                for (int j = i + 1; j < lim; j++) for (int k = 0; k < sz * 2; ++k) w[j][k] += 1ll * T[k] * p[dep][j - i - 1][k];
            }
        }
    }

    void exp(Poly &res, int l, int r, int n, int dep = 0) {
        if (r - l <= 256) {
            r = min(r, n);
            for (int i = l; i < r; ++i) {
                if (i == 0) res[i] = 1; else res[i] = 1ll * res[i] * inv[i] % mod;
                for (int j = i + 1; j < r; ++j) res[j] = (res[j] + 1ll * res[i] * A[j - i] % mod * (j - i)) % mod;
            }
            return;
        }
        int sz = r - l >> 4;
        vector<LL> w[16];
        Poly T(sz * 2);
        int lim = 0;
        for (; lim < 16; lim++) {
            if (l + lim * sz >= n) break;
            w[lim].resize(sz << 1);
        }
        for (int i = 0; i < lim; i++) {
            if (i) {
                for (int j = 0; j < sz * 2; j++) T[j] = w[i][j] % mod;
                NTT(T.data(), sz * 2, -1);
                for (int j = 0; j < sz; j++) Inc(res[l + i * sz + j], T[sz + j]);
            }
            exp(res, l + i * sz, l + (i + 1) * sz, n, dep + 1);
            if (i < lim - 1) {
                for (int j = 0; j < sz; j++) T[j + sz] = 0, T[j] = res[l + i * sz + j];
                NTT(T.data(), sz * 2, 1);
                for (int j = i + 1; j < lim; j++) for (int k = 0; k < sz * 2; ++k) w[j][k] += 1ll * T[k] * p[dep][j - i - 1][k];
            }
        }
    }
}

Poly Exp(Poly A) {
    int n = A.size(), l = 1 << lg[n] + 1;
    A.resize(l << 1);
    Poly res(l);
    SemiConvol::A = A;
    for (int le = l, dep = 0; le > 256; le >>= 4, dep++) {
        int sz = le >> 4;
        for (int i = 0; i < 16; i++) {
            SemiConvol::p[dep][i].resize(sz * 2);
            for (int j = 0; j < (sz << 1); j++) SemiConvol::p[dep][i][j] = 1ll * A[i * sz + j] * (i * sz + j) % mod;
            NTT(SemiConvol::p[dep][i].data(), sz * 2, 1);
        }
    }
    SemiConvol::exp(res, 0, l, n);
    res.resize(n);
    return res;
}

Poly Ln(Poly A) {
    int n = A.size(), l = 1 << lg[n] + 1;
    A.resize(l << 1);
    Poly res(l);
    SemiConvol::A = A;
    for (int le = l, dep = 0; le > 256; le >>= 4, dep++) {
        int sz = le >> 4;
        for (int i = 0; i < 16; i++) {
            SemiConvol::p[dep][i].resize(sz * 2);
            for (int j = 0; j < (sz << 1); j++) SemiConvol::p[dep][i][j] = 1ll * A[i * sz + j] % mod;
            NTT(SemiConvol::p[dep][i].data(), sz * 2, 1);
        }
    }
    SemiConvol::ln(res, 0, l, n);
    res.resize(n);
    return res;
}

inline Poly Sqrt_Rec(Poly A) {
    static int t[maxn];
    int n = A.size();
    A.resize(n << 1);
    Poly C{Pow(Math::work(A[0]), mod - 2)};
    for (int k = 2; k < (n << 1); k <<= 1) {
        Poly B = C;
        B.resize(k << 1);
        memcpy(t, A.data(), k << 2);
        NTT(B.data(), k << 1, 1);
        NTT(t, k << 1, 1);
        for (int i = 0; i < (k << 1); i++) t[i] = 1ll * B[i] * t[i] % mod * B[i] % mod * B[i] % mod;
        NTT(t, k << 1, -1);
        C.resize(k);
        for (int i = (k >> 1); i < k; i++) C[i] = t[i] ? mod - 1ll * inv2 * t[i] % mod : 0;
    }
    C.resize(n);
    return C;
}

inline Poly Pow(Poly A, int k) {
    int n = A.size();
    A = Ln(A);
    for (int i = 1; i < n; i++) A[i] = 1ll * A[i] * k % mod;
    return Exp(A);
}

inline int Init(int n) {
    int m;
    for (m = 1; m <= n; m <<= 1);
    init(m);
    return m;
}

int n, k, m;
Poly a;
int nn, mm, kk;
int AAA[N];

void solve() {
    Combinatorial_mathematics Ci(2000001);
    cin >> nn >> mm >> kk;
    a.resize(mm + 1);
    init(mm + 1);
    for (int i = 0; i <= mm; i++) a[i] = 1ll * Ci.C(2 * i, i) * Ci.Inv(i + 1) % mod;
    a[kk] = 0;
    // vec = a[0-m]
    // res = vec^n;
    // cout << res[m];
    a = Pow(a, nn);
    cout << a[mm] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
//    cin >> _;
    for (int o = 1; o <= _; o++) {
        //      cout << "Case #<<" << o << ": ";
        solve();
    }
    return 0;
}

/*





*/

详细

Test #1:

score: 100
Accepted
time: 17ms
memory: 24804kb

input:

2 2 1

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 16ms
memory: 24920kb

input:

1 1 1

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 22ms
memory: 24872kb

input:

24 120 30

output:

379268651

result:

ok answer is '379268651'

Test #4:

score: 0
Accepted
time: 18ms
memory: 25060kb

input:

1451 1598 1130

output:

884873572

result:

ok answer is '884873572'

Test #5:

score: 0
Accepted
time: 18ms
memory: 25148kb

input:

1324 1742 1033

output:

856733047

result:

ok answer is '856733047'

Test #6:

score: 0
Accepted
time: 19ms
memory: 25060kb

input:

1378 1614 1335

output:

869903701

result:

ok answer is '869903701'

Test #7:

score: 0
Accepted
time: 22ms
memory: 25072kb

input:

1071 1907 1281

output:

327700529

result:

ok answer is '327700529'

Test #8:

score: 0
Accepted
time: 18ms
memory: 24772kb

input:

1204 1337 1277

output:

475981175

result:

ok answer is '475981175'

Test #9:

score: 0
Accepted
time: 18ms
memory: 24868kb

input:

146 246 100

output:

404402509

result:

ok answer is '404402509'

Test #10:

score: 0
Accepted
time: 20ms
memory: 24840kb

input:

226 183 144

output:

351921989

result:

ok answer is '351921989'

Test #11:

score: 0
Accepted
time: 17ms
memory: 24916kb

input:

234 287 158

output:

658959115

result:

ok answer is '658959115'

Test #12:

score: 0
Accepted
time: 17ms
memory: 24776kb

input:

242 156 122

output:

325586111

result:

ok answer is '325586111'

Test #13:

score: 0
Accepted
time: 16ms
memory: 24896kb

input:

168 271 135

output:

181613866

result:

ok answer is '181613866'

Test #14:

score: 0
Accepted
time: 17ms
memory: 24776kb

input:

22 25 1

output:

684860973

result:

ok answer is '684860973'

Test #15:

score: 0
Accepted
time: 20ms
memory: 24796kb

input:

45 22 15

output:

217501624

result:

ok answer is '217501624'

Test #16:

score: 0
Accepted
time: 17ms
memory: 24788kb

input:

47 29 16

output:

690840771

result:

ok answer is '690840771'

Test #17:

score: 0
Accepted
time: 17ms
memory: 24848kb

input:

2 25 25

output:

660660974

result:

ok answer is '660660974'

Test #18:

score: 0
Accepted
time: 17ms
memory: 24808kb

input:

32 34 11

output:

133387056

result:

ok answer is '133387056'

Test #19:

score: 0
Accepted
time: 71ms
memory: 34244kb

input:

88196 118335 104471

output:

7192211

result:

ok answer is '7192211'

Test #20:

score: 0
Accepted
time: 56ms
memory: 28560kb

input:

142215 57117 51272

output:

627598793

result:

ok answer is '627598793'

Test #21:

score: 0
Accepted
time: 71ms
memory: 30480kb

input:

102255 60360 51525

output:

447649003

result:

ok answer is '447649003'

Test #22:

score: 0
Accepted
time: 56ms
memory: 33496kb

input:

132449 83413 54230

output:

215816803

result:

ok answer is '215816803'

Test #23:

score: 0
Accepted
time: 64ms
memory: 33920kb

input:

68499 95762 77190

output:

393029560

result:

ok answer is '393029560'

Test #24:

score: 0
Accepted
time: 761ms
memory: 90744kb

input:

751951 751951 1

output:

804170883

result:

ok answer is '804170883'

Test #25:

score: 0
Accepted
time: 15ms
memory: 25108kb

input:

804420 1962 410

output:

869056555

result:

ok answer is '869056555'

Test #26:

score: 0
Accepted
time: 76ms
memory: 28632kb

input:

828607 63739 13

output:

926542030

result:

ok answer is '926542030'

Test #27:

score: 0
Accepted
time: 27ms
memory: 28636kb

input:

472167 20529 23

output:

142703540

result:

ok answer is '142703540'

Test #28:

score: 0
Accepted
time: 281ms
memory: 57804kb

input:

363438 363438 1

output:

764563597

result:

ok answer is '764563597'

Test #29:

score: 0
Accepted
time: 999ms
memory: 95508kb

input:

1000000 1000000 628333

output:

283487375

result:

ok answer is '283487375'

Test #30:

score: 0
Accepted
time: 1001ms
memory: 97808kb

input:

1000000 1000000 900084

output:

651386967

result:

ok answer is '651386967'

Test #31:

score: 0
Accepted
time: 1010ms
memory: 97820kb

input:

1000000 1000000 27328

output:

621963453

result:

ok answer is '621963453'

Test #32:

score: 0
Accepted
time: 1012ms
memory: 95896kb

input:

1000000 1000000 538409

output:

997879100

result:

ok answer is '997879100'

Test #33:

score: 0
Accepted
time: 1005ms
memory: 94512kb

input:

1000000 1000000 928121

output:

964724707

result:

ok answer is '964724707'

Test #34:

score: 0
Accepted
time: 681ms
memory: 88348kb

input:

685624 665877 563708

output:

257429683

result:

ok answer is '257429683'

Test #35:

score: 0
Accepted
time: 939ms
memory: 93516kb

input:

692290 942095 553970

output:

82511143

result:

ok answer is '82511143'

Test #36:

score: 0
Accepted
time: 768ms
memory: 88092kb

input:

579579 765702 631728

output:

954001361

result:

ok answer is '954001361'

Test #37:

score: 0
Accepted
time: 650ms
memory: 85788kb

input:

756854 634736 567170

output:

393747028

result:

ok answer is '393747028'

Test #38:

score: 0
Accepted
time: 1001ms
memory: 96004kb

input:

649175 997874 511181

output:

242172216

result:

ok answer is '242172216'

Test #39:

score: 0
Accepted
time: 1003ms
memory: 92992kb

input:

786431 1000000 999999

output:

627359027

result:

ok answer is '627359027'