QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290537 | #4472. 珍珠 | MoRanSky | 100 ✓ | 58ms | 13344kb | C++23 | 4.0kb | 2023-12-25 05:39:59 | 2023-12-25 05:39:59 |
Judging History
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