QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101283#1816. Multiple ParenthesesckisekiAC ✓1976ms134632kbC++203.7kb2023-04-29 04:45:202023-04-29 04:45:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-29 04:45:25]
  • 评测
  • 测评结果:AC
  • 用时:1976ms
  • 内存:134632kb
  • [2023-04-29 04:45:20]
  • 提交

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'