QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290537#4472. 珍珠MoRanSky100 ✓58ms13344kbC++234.0kb2023-12-25 05:39:592023-12-25 05:39:59

Judging History

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

  • [2023-12-25 05:39:59]
  • 评测
  • 测评结果:100
  • 用时:58ms
  • 内存:13344kb
  • [2023-12-25 05:39:59]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

typedef vector<int> Poly;

#define pb push_back

const int N = 8e5 + 5, P = 998244353, G = 3;

int A[N], rev[N], fact[N], infact[N];
int lim = 1, len = 0, W[20][N];

int inline power(int a, int b, int Mod = P) {
	int res = 1;
	while (b) {
		if (b & 1) res = (LL)res * a % Mod;
		a = (LL)a * a % Mod;
		b >>= 1;
	}
	return res;
}


int Gi = power(G, P - 2, P), inv2 = power(2, P - 2, P);

void inline factPrework(int n) {
	fact[0] = infact[0] = 1;
	for (int i = 1; i <= n; i++) fact[i] = (LL)fact[i - 1] * i % P;
	infact[n] = power(fact[n], P - 2);
	for (int i = n - 1; i; i--) infact[i] = infact[i + 1] * (i + 1ll) % P;
}


void inline NTT(int c[], int lim, int o) {
	for (int i = 0; i < lim; i++)
		if (i < rev[i]) swap(c[i], c[rev[i]]);
	for (int k = 1, t = 0; k < lim; k <<= 1, t++) {
		for (int i = 0; i < lim; i += (k << 1)) {
			for (int j = 0; j < k; j++) {
				int u = c[i + j], v = (LL)c[i + k + j] * W[t][j] % P;
				c[i + j] = u + v >= P ? u + v - P : u + v;
				c[i + j + k] = u - v < 0 ? u - v + P : u - v; 
			}
		}
	}
	if (o == -1) {
		reverse(c + 1, c + lim);
		int inv = power(lim, P - 2, P);
		for (int i = 0; i < lim; i++)
			c[i] = (LL)c[i] * inv % P;
	}
}

void inline setN(int n) {
	lim = 1, len = 0;
	while (lim < n) lim <<= 1, len++;
	for (int i = 0; i < lim; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
}

Poly inline NTT(Poly a, int o) {
	int n = a.size();
	for (int i = 0; i < n; i++) A[i] = a[i];
	NTT(A, lim, o);
	a.clear();
	for (int i = 0; i < lim; i++) a.push_back(A[i]), A[i] = 0;
	return a;
}
Poly inline mul (Poly a, Poly b, int newn = -1) {
	if (newn == -1) newn = a.size() + b.size() - 1;
	setN(a.size() + b.size() - 1);
	Poly c = NTT(a, 1), d = NTT(b, 1);
	for (int i = 0; i < lim; i++) c[i] = (LL)c[i] * d[i] % P;
	d = NTT(c, -1); d.resize(newn);
	return d;
}
// 用到的最大的 n
void inline init(int n) {
	factPrework(n);
	setN(2 * n + 1);
	for (int k = 1, t = 0; k < lim; k <<= 1, t++) {
		int wn = power(G, (P - 1) / (k << 1));
		W[t][0] = 1;
		for (int j = 1; j < k; j++) W[t][j] = (LL)W[t][j - 1] * wn % P;
	}
}


int inline C(int a, int b) {
    if (a < b || a < 0 || b < 0) return 0;
    return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}

int D, n, m, L, f[N], g[N];

void inline del(int &x, int y) {
	x -= y;
	if (x < 0) x += P;
}


void inline add(int &x, int y) {
    x += y;
    if (x >= P) x -= P;
}


int main() {
	read(D), read(n), read(m);
    init(D + 1);
    L = n - 2 * m;
    if (L >= D) {
    	printf("%d\n", power(D, n));
    	return 0;
    } else if (L < 0) {
    	puts("0");
    	return 0;
    }
    int v = 1;
    Poly A(D + 1, 0);
    Poly B(D + 1, 0);
    for (int i = 0; i <= D; i++) A[i] = infact[i];
    for (int i = 0; i <= D; i++) {
    	B[i] = 1ll * infact[i] * power((D - 2 * i + P) % P, n) % P;
    	if (i & 1) B[i] = P - B[i];
    }
  
    Poly Z = mul(A, B);
    for (int k = 0; k <= D; k++) {
    	add(f[k], 1ll * C(D, k) * v % P * Z[k] % P * fact[k] % P);
    	v = 1ll * v * inv2 % P;
    }
    A.resize(D + 1, 0);
    B.resize(D + 1, 0);
    for (int i = 0; i <= D; i++) A[D - i] = 1ll * fact[i] * f[i] % P;
    for (int i = 0; i <= D; i++) B[i] = 1ll * infact[i] * ((i & 1) ? P - 1 : 1) % P;
    Z = mul(A, B);
    int ans = 0;
    for (int i = 0; i <= L; i++) {
    	add(ans, 1ll * Z[D - i] * infact[i] % P);
    }
    printf("%d\n", ans);
    return 0;
}

详细

Test #1:

score: 4
Accepted
time: 0ms
memory: 3664kb

input:

2 7 3

output:

128

result:

ok 1 number(s): "128"

Test #2:

score: 4
Accepted
time: 1ms
memory: 3704kb

input:

2 20 9

output:

1048576

result:

ok 1 number(s): "1048576"

Test #3:

score: 4
Accepted
time: 1ms
memory: 3796kb

input:

99 97 30

output:

893559494

result:

ok 1 number(s): "893559494"

Test #4:

score: 4
Accepted
time: 1ms
memory: 3800kb

input:

100 97 29

output:

870441375

result:

ok 1 number(s): "870441375"

Test #5:

score: 4
Accepted
time: 1ms
memory: 3680kb

input:

97 100 16

output:

114531619

result:

ok 1 number(s): "114531619"

Test #6:

score: 4
Accepted
time: 1ms
memory: 3728kb

input:

98 98 38

output:

910698957

result:

ok 1 number(s): "910698957"

Test #7:

score: 4
Accepted
time: 1ms
memory: 3756kb

input:

100 99 30

output:

267167918

result:

ok 1 number(s): "267167918"

Test #8:

score: 4
Accepted
time: 2ms
memory: 3988kb

input:

4000 3998 602

output:

267823033

result:

ok 1 number(s): "267823033"

Test #9:

score: 4
Accepted
time: 4ms
memory: 4076kb

input:

3999 3998 478

output:

7661427

result:

ok 1 number(s): "7661427"

Test #10:

score: 4
Accepted
time: 2ms
memory: 4116kb

input:

4000 3999 18

output:

46680613

result:

ok 1 number(s): "46680613"

Test #11:

score: 4
Accepted
time: 2ms
memory: 3996kb

input:

4000 3998 683

output:

689956672

result:

ok 1 number(s): "689956672"

Test #12:

score: 4
Accepted
time: 2ms
memory: 3988kb

input:

3998 3998 1743

output:

625630497

result:

ok 1 number(s): "625630497"

Test #13:

score: 4
Accepted
time: 1ms
memory: 3772kb

input:

300 999999997 499999880

output:

311178114

result:

ok 1 number(s): "311178114"

Test #14:

score: 4
Accepted
time: 1ms
memory: 3720kb

input:

297 999999999 499999955

output:

111728734

result:

ok 1 number(s): "111728734"

Test #15:

score: 4
Accepted
time: 1ms
memory: 3720kb

input:

298 999999998 499999978

output:

873407954

result:

ok 1 number(s): "873407954"

Test #16:

score: 4
Accepted
time: 4ms
memory: 6528kb

input:

100000 999999998 0

output:

403169128

result:

ok 1 number(s): "403169128"

Test #17:

score: 4
Accepted
time: 41ms
memory: 13272kb

input:

99999 100000 1

output:

520922757

result:

ok 1 number(s): "520922757"

Test #18:

score: 4
Accepted
time: 43ms
memory: 13312kb

input:

99998 99998 2

output:

776350879

result:

ok 1 number(s): "776350879"

Test #19:

score: 4
Accepted
time: 54ms
memory: 13316kb

input:

99998 999999998 499972261

output:

805937760

result:

ok 1 number(s): "805937760"

Test #20:

score: 4
Accepted
time: 53ms
memory: 13284kb

input:

99997 999999999 499975678

output:

265933807

result:

ok 1 number(s): "265933807"

Test #21:

score: 4
Accepted
time: 57ms
memory: 13304kb

input:

100000 1000000000 499958129

output:

59384653

result:

ok 1 number(s): "59384653"

Test #22:

score: 4
Accepted
time: 58ms
memory: 13344kb

input:

99998 999999999 499978565

output:

897679746

result:

ok 1 number(s): "897679746"

Test #23:

score: 4
Accepted
time: 46ms
memory: 13276kb

input:

100000 999999999 499970692

output:

169325977

result:

ok 1 number(s): "169325977"

Test #24:

score: 4
Accepted
time: 53ms
memory: 13328kb

input:

99997 1000000000 499976402

output:

562099965

result:

ok 1 number(s): "562099965"

Test #25:

score: 4
Accepted
time: 53ms
memory: 13320kb

input:

99997 1000000000 499978285

output:

681053406

result:

ok 1 number(s): "681053406"

Extra Test:

score: 0
Extra Test Passed