QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122947 | #1816. Multiple Parentheses | Scarlett_boy | AC ✓ | 1012ms | 97820kb | C++17 | 9.4kb | 2023-07-11 15:36:40 | 2023-07-11 15:36:41 |
Judging History
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'