ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203192 | #3546. count | yllcm | 100 | 7730ms | 111804kb | C++ | 3.6kb | 2024-02-20 11:10:37 | 2024-02-20 13:44:49 |
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 1e7 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
int res = 1;
for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
return res;
}
int fac[N], ifac[N], pw[N], ipw[N];
void init() {
fac[0] = ifac[0] = 1;
for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
ifac[N - 1] = ksm(fac[N - 1], P - 2);
for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
for(int i = 1; i < N; i <<= 1)pw[i] = ksm(3, (P - 1) / i);
for(int i = 1; i < N; i <<= 1)ipw[i] = ksm(pw[i], P - 2);
return ;
}
int com(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int n, m, x;
int pre[N], suf[N], f[N], g[N], h[N], rev[N];
void NTT(int *f, int len, int op) {
for(int i = 0; i < len; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
for(int i = 0; i < len; i++)if(i < rev[i])swap(f[i], f[rev[i]]);
for(int k = 1; k < len; k <<= 1) {
for(int i = 0; i < len; i += k + k) {
int gn = (op == 1 ? pw[k + k] : ipw[k + k]), g = 1;
for(int j = 0; j < k; j++, g = 1ll * g * gn % P) {
int x = f[i + j], y = 1ll * g * f[i + j + k] % P;
f[i + j] = (x + y) % P;
f[i + j + k] = (x - y + P) % P;
}
}
}
if(op == -1) {
int inv = ksm(len, P - 2);
for(int i = 0; i < len; i++)f[i] = 1ll * f[i] * inv % P;
}
return ;
}
int main() {
init();
n = read(); m = read(); x = read();
int ans = 0;
suf[n + 1] = suf[n + 2] = 1;
for(int i = n; i; i--)suf[i] = 1ll * suf[i + 1] * (n - (i - 1)) % P;
for(int i = 1; i < x; i++)f[i] = 1ll * (i - 1) * fac[n - i - 1] % P;
for(int i = 0; i <= n; i++)g[i] = ifac[i];
int ln = 1;
while(ln < (n + n + 5))ln <<= 1;
NTT(f, ln, 1); NTT(g, ln, 1);
for(int i = 0; i < ln; i++)f[i] = 1ll * f[i] * g[i] % P;
NTT(f, ln, -1);
// for(int i = 0; i < ln; i++)cout << f[i] << ' '; cout << endl;
for(int r = 1; r < n; r++) {
int res = com(r - 1 + m, m + 1);
res = 1ll * res * suf[r + 2] % P;
res = 1ll * res * f[n - r + 1] % P;
add(ans, res);
}
if(x > 1) {
int res = com(n - 1 + m, m + 1);
res = 1ll * res * fac[n - 2] % P;
add(ans, res);
}
for(int i = 0; i < ln; i++)f[i] = g[i] = 0;
for(int i = 1; i < x; i++)f[i] = fac[n - i + 1];
for(int i = 1; i <= n; i++)g[i] = ifac[i];
// for(int v = 1; v < x; v++) {
// pre[1] = 1;
// for(int i = 2; i <= n; i++)pre[i] = 1ll * pre[i - 1] * (n - v - (i - 1)) % P;
// for(int r = 1; r <= n; r++) {
// int res = com(r - 1 + m, m + 1);
// res = 1ll * res * pre[r - 1] % P;
// res = 1ll * res * suf[r + 2] % P;
// if(r < n)res = 1ll * res * (v - 1) % P;
// add(ans, res);
// }
// }
pre[1] = 1;
for(int i = 2; i <= n; i++)pre[i] = 1ll * pre[i - 1] * (n - x + 1 - (i - 1)) % P;
for(int r = 1; r <= n; r++) {
int res = com(r - 1 + m, m);
res = 1ll * res * pre[r] % P;
if(r < n)res = 1ll * res * (x - 1) % P;
res = 1ll * res * suf[r + 2] % P;
add(ans, res);
}
printf("%d\n", ans);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 112ms
memory: 79412kb
input:
7 3 7
output:
20640
result:
ok single line: '20640'
Test #2:
score: 5
Accepted
time: 108ms
memory: 79412kb
input:
7 2 6
output:
10560
result:
ok single line: '10560'
Test #3:
score: 5
Accepted
time: 120ms
memory: 79420kb
input:
178 88 176
output:
263756452
result:
ok single line: '263756452'
Test #4:
score: 5
Accepted
time: 131ms
memory: 79416kb
input:
165 64 151
output:
675678116
result:
ok single line: '675678116'
Test #5:
score: 5
Accepted
time: 133ms
memory: 79420kb
input:
188 83 184
output:
69478022
result:
ok single line: '69478022'
Test #6:
score: 5
Accepted
time: 102ms
memory: 79420kb
input:
158 62 144
output:
203749473
result:
ok single line: '203749473'
Test #7:
score: 5
Accepted
time: 128ms
memory: 79476kb
input:
1974 459 1845
output:
535987457
result:
ok single line: '535987457'
Test #8:
score: 5
Accepted
time: 137ms
memory: 79480kb
input:
1970 499 1944
output:
118089661
result:
ok single line: '118089661'
Test #9:
score: 5
Accepted
time: 137ms
memory: 79476kb
input:
1962 195 1766
output:
563043519
result:
ok single line: '563043519'
Test #10:
score: 5
Accepted
time: 134ms
memory: 79476kb
input:
1957 408 1858
output:
368025374
result:
ok single line: '368025374'
Test #11:
score: 5
Accepted
time: 679ms
memory: 111804kb
input:
999966 2907 1
output:
891313743
result:
ok single line: '891313743'
Test #12:
score: 5
Accepted
time: 651ms
memory: 111800kb
input:
999997 4828 2
output:
815004193
result:
ok single line: '815004193'
Test #13:
score: 5
Accepted
time: 656ms
memory: 111804kb
input:
999959 5271 2
output:
600125008
result:
ok single line: '600125008'
Test #14:
score: 5
Accepted
time: 632ms
memory: 111800kb
input:
999961 24134 10
output:
784444417
result:
ok single line: '784444417'
Test #15:
score: 5
Accepted
time: 636ms
memory: 111800kb
input:
999983 33966 10
output:
744109998
result:
ok single line: '744109998'
Test #16:
score: 5
Accepted
time: 658ms
memory: 111804kb
input:
999951 31503 999934
output:
518818294
result:
ok single line: '518818294'
Test #17:
score: 5
Accepted
time: 636ms
memory: 111804kb
input:
999953 21775 999941
output:
459927485
result:
ok single line: '459927485'
Test #18:
score: 5
Accepted
time: 636ms
memory: 111800kb
input:
999970 7889 999782
output:
979137112
result:
ok single line: '979137112'
Test #19:
score: 5
Accepted
time: 641ms
memory: 111804kb
input:
999972 6809 999964
output:
64469239
result:
ok single line: '64469239'
Test #20:
score: 5
Accepted
time: 663ms
memory: 111804kb
input:
999952 29898 999948
output:
801924273
result:
ok single line: '801924273'
Extra Test:
score: 0
Extra Test Passed