QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101283 | #1816. Multiple Parentheses | ckiseki | AC ✓ | 1976ms | 134632kb | C++20 | 3.7kb | 2023-04-29 04:45:20 | 2023-04-29 04:45:25 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int maxn = 1 << 22;
constexpr int mod = 998244353;
constexpr int G = 3;
constexpr int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
constexpr int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
constexpr int mul(int64_t a, int64_t b) {
return static_cast<int>(a * b % mod);
}
constexpr int mpow(int a, int64_t k) {
int r = 1;
while (k) {
if (k & 1) r = mul(r, a);
k >>= 1;
a = mul(a, a);
}
return r;
}
int minv_small_tbl[maxn];
int minv_small(int a) {
return minv_small_tbl[a];
}
constexpr int minv(int a) {
return mpow(a, mod - 2);
}
int fac[maxn], ifac[maxn];
int comb(int a, int b) {
return mul(fac[a], mul(ifac[b], ifac[a - b]));
}
void init() {
fac[0] = 1;
for (int i = 1; i < maxn; ++i)
fac[i] = mul(fac[i - 1], i);
ifac[maxn - 1] = minv(fac[maxn - 1]);
for (int i = maxn - 2; i >= 0; --i)
ifac[i] = mul(ifac[i + 1], i + 1);
for (int i = 1; i < maxn; ++i)
minv_small_tbl[i] = mul(ifac[i], fac[i - 1]);
}
template <int n>
using P = array<int, 1 << n>;
template <int n>
concept pw2 = ((n != 0) and ((n & (-n)) == n));
struct NTT {
int roots[maxn];
NTT() {
int r = mpow(G, (mod - 1) / maxn);
for (int i = maxn >> 1; i; i >>= 1) {
roots[i] = 1;
for (int j = 1; j < i; j++)
roots[i + j] = mul(roots[i + j - 1], r);
r = mul(r, r);
}
}
template <int n>
requires pw2<n>
void trans(int F[], bool inv = false) {
for (int i = 0, j = 0; i < n; ++i) {
if (i < j) swap(F[i], F[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (int s = 1; s < n; s *= 2) {
for (int i = 0; i < n; i += s * 2) {
for (int j = 0; j < s; ++j) {
int a = F[i + j];
int b = mul(F[i + j + s], roots[s + j]);
F[i + j] = add(a, b);
F[i + j + s] = sub(a, b);
}
}
}
if (inv) {
int invn = minv_small(n);
for (int i = 0; i < n; ++i)
F[i] = mul(F[i], invn);
reverse(F + 1, F + n);
}
}
};
NTT ntt;
template <int n>
requires pw2<n>
void Mul(int a[], int b[]) {
fill_n(a + n, n, 0), fill_n(b + n, n, 0);
ntt.trans<n * 2>(a), ntt.trans<n * 2>(b);
for (int i = 0; i < n * 2; ++i)
a[i] = mul(a[i], b[i]);
ntt.trans<n * 2>(a, true);
}
template <int n>
requires pw2<n>
void Inv(const int a[], int b[]) {
if constexpr (n == 1) {
b[0] = minv(a[0]);
} else {
static int c[n * 2];
Inv<n / 2>(a, b), fill_n(b + n / 2, n / 2 * 3, 0);
copy_n(a, n, c), fill_n(c + n, n, 0);
ntt.trans<n * 2>(b), ntt.trans<n * 2>(c);
for (int i = 0; i < n * 2; ++i)
b[i] = mul(b[i], sub(2, mul(b[i], c[i])));
ntt.trans<n * 2>(b, true);
}
}
template <int n>
requires pw2<n>
void Ln(const int a[], int b[]) {
static int c[n * 2];
Inv<n>(a, c);
for (int i = 0; i + 1 < n; ++i)
b[i] = mul(i + 1, a[i + 1]);
b[n - 1] = 0;
Mul<n>(b, c);
for (int i = n - 2; i >= 0; --i)
b[i + 1] = mul(minv_small(i + 1), b[i]);
b[0] = 0;
}
template <int n>
requires pw2<n>
void Exp(const int a[], int b[]) {
if constexpr (n == 1) {
b[0] = 1;
} else {
static int c[n * 2];
Exp<n / 2>(a, b), fill_n(b + n / 2, n / 2, 0);
Ln<n>(b, c);
c[0] = mod - 1;
for (int i = 0; i < n; ++i)
c[i] = sub(a[i], c[i]);
Mul<n>(b, c);
}
}
int a[maxn], b[maxn];
} // namespace
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
init();
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i <= m; ++i) {
if (i == k) continue;
a[i] = mul(comb(2 * i, i), minv_small(i + 1));
}
constexpr int m2 = 1 << 20;
Ln<m2>(a, b);
for (int i = 0; i < m2; ++i)
b[i] = mul(b[i], n);
Exp<m2>(b, a);
cout << a[m] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1956ms
memory: 134524kb
input:
2 2 1
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 1922ms
memory: 134528kb
input:
1 1 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 1965ms
memory: 134512kb
input:
24 120 30
output:
379268651
result:
ok answer is '379268651'
Test #4:
score: 0
Accepted
time: 1924ms
memory: 134376kb
input:
1451 1598 1130
output:
884873572
result:
ok answer is '884873572'
Test #5:
score: 0
Accepted
time: 1921ms
memory: 134464kb
input:
1324 1742 1033
output:
856733047
result:
ok answer is '856733047'
Test #6:
score: 0
Accepted
time: 1935ms
memory: 134384kb
input:
1378 1614 1335
output:
869903701
result:
ok answer is '869903701'
Test #7:
score: 0
Accepted
time: 1907ms
memory: 134628kb
input:
1071 1907 1281
output:
327700529
result:
ok answer is '327700529'
Test #8:
score: 0
Accepted
time: 1941ms
memory: 134612kb
input:
1204 1337 1277
output:
475981175
result:
ok answer is '475981175'
Test #9:
score: 0
Accepted
time: 1945ms
memory: 134472kb
input:
146 246 100
output:
404402509
result:
ok answer is '404402509'
Test #10:
score: 0
Accepted
time: 1966ms
memory: 134632kb
input:
226 183 144
output:
351921989
result:
ok answer is '351921989'
Test #11:
score: 0
Accepted
time: 1918ms
memory: 134432kb
input:
234 287 158
output:
658959115
result:
ok answer is '658959115'
Test #12:
score: 0
Accepted
time: 1942ms
memory: 134436kb
input:
242 156 122
output:
325586111
result:
ok answer is '325586111'
Test #13:
score: 0
Accepted
time: 1939ms
memory: 134472kb
input:
168 271 135
output:
181613866
result:
ok answer is '181613866'
Test #14:
score: 0
Accepted
time: 1938ms
memory: 134432kb
input:
22 25 1
output:
684860973
result:
ok answer is '684860973'
Test #15:
score: 0
Accepted
time: 1947ms
memory: 134380kb
input:
45 22 15
output:
217501624
result:
ok answer is '217501624'
Test #16:
score: 0
Accepted
time: 1960ms
memory: 134432kb
input:
47 29 16
output:
690840771
result:
ok answer is '690840771'
Test #17:
score: 0
Accepted
time: 1942ms
memory: 134468kb
input:
2 25 25
output:
660660974
result:
ok answer is '660660974'
Test #18:
score: 0
Accepted
time: 1943ms
memory: 134516kb
input:
32 34 11
output:
133387056
result:
ok answer is '133387056'
Test #19:
score: 0
Accepted
time: 1933ms
memory: 134460kb
input:
88196 118335 104471
output:
7192211
result:
ok answer is '7192211'
Test #20:
score: 0
Accepted
time: 1960ms
memory: 134468kb
input:
142215 57117 51272
output:
627598793
result:
ok answer is '627598793'
Test #21:
score: 0
Accepted
time: 1909ms
memory: 134520kb
input:
102255 60360 51525
output:
447649003
result:
ok answer is '447649003'
Test #22:
score: 0
Accepted
time: 1951ms
memory: 134616kb
input:
132449 83413 54230
output:
215816803
result:
ok answer is '215816803'
Test #23:
score: 0
Accepted
time: 1907ms
memory: 134580kb
input:
68499 95762 77190
output:
393029560
result:
ok answer is '393029560'
Test #24:
score: 0
Accepted
time: 1964ms
memory: 134432kb
input:
751951 751951 1
output:
804170883
result:
ok answer is '804170883'
Test #25:
score: 0
Accepted
time: 1914ms
memory: 134464kb
input:
804420 1962 410
output:
869056555
result:
ok answer is '869056555'
Test #26:
score: 0
Accepted
time: 1965ms
memory: 134516kb
input:
828607 63739 13
output:
926542030
result:
ok answer is '926542030'
Test #27:
score: 0
Accepted
time: 1976ms
memory: 134464kb
input:
472167 20529 23
output:
142703540
result:
ok answer is '142703540'
Test #28:
score: 0
Accepted
time: 1973ms
memory: 134524kb
input:
363438 363438 1
output:
764563597
result:
ok answer is '764563597'
Test #29:
score: 0
Accepted
time: 1934ms
memory: 134428kb
input:
1000000 1000000 628333
output:
283487375
result:
ok answer is '283487375'
Test #30:
score: 0
Accepted
time: 1964ms
memory: 134460kb
input:
1000000 1000000 900084
output:
651386967
result:
ok answer is '651386967'
Test #31:
score: 0
Accepted
time: 1967ms
memory: 134616kb
input:
1000000 1000000 27328
output:
621963453
result:
ok answer is '621963453'
Test #32:
score: 0
Accepted
time: 1958ms
memory: 134452kb
input:
1000000 1000000 538409
output:
997879100
result:
ok answer is '997879100'
Test #33:
score: 0
Accepted
time: 1968ms
memory: 134632kb
input:
1000000 1000000 928121
output:
964724707
result:
ok answer is '964724707'
Test #34:
score: 0
Accepted
time: 1919ms
memory: 134448kb
input:
685624 665877 563708
output:
257429683
result:
ok answer is '257429683'
Test #35:
score: 0
Accepted
time: 1954ms
memory: 134436kb
input:
692290 942095 553970
output:
82511143
result:
ok answer is '82511143'
Test #36:
score: 0
Accepted
time: 1958ms
memory: 134632kb
input:
579579 765702 631728
output:
954001361
result:
ok answer is '954001361'
Test #37:
score: 0
Accepted
time: 1920ms
memory: 134464kb
input:
756854 634736 567170
output:
393747028
result:
ok answer is '393747028'
Test #38:
score: 0
Accepted
time: 1929ms
memory: 134516kb
input:
649175 997874 511181
output:
242172216
result:
ok answer is '242172216'
Test #39:
score: 0
Accepted
time: 1942ms
memory: 134508kb
input:
786431 1000000 999999
output:
627359027
result:
ok answer is '627359027'