ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203182 | #3546. count | shr | 100 | 1164ms | 20788kb | C++11 | 969b | 2024-02-20 10:29:00 | 2024-02-20 13:43:58 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5,mod=998244353;
int n,k,X,ans,p[N],iv[N],f[N];
inline void fix(int&x) {if(x>=mod) x-=mod;}
int qpow(int x,int y){
int res=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
return res;
}
int c(int x,int y){
if(x<y||y<0) return 0;
return 1ll*p[x]*iv[y]%mod*iv[x-y]%mod;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>k>>X;
for(int i=p[0]=1;i<N;i++) p[i]=1ll*i*p[i-1]%mod;
iv[N-1]=qpow(p[N-1],mod-2);
for(int i=N-2;~i;i--) iv[i]=iv[i+1]*(i+1ll)%mod;
if(X==1) ans=1ll*p[n-1]*c(k+n-1,k)%mod;
else for(int i=2;i<=n;i++) fix(ans+=1ll*p[n-2]*c(k+n-i,k)%mod);
for(int i=1;i<n;i++)
fix(ans+=(X-1ll)*c(n-X,i-1)%mod*p[i-1]%mod*p[n-i-1]%mod*c(k+i-1,k)%mod);
for(int i=f[0]=1;i<n;i++) f[i]=(f[i-1]+c(k+i,k))%mod;
for(int i=2;i<n;i++)
fix(ans+=(c(n-1,i)-c(n-X,i)-(X-1ll)*c(n-X,i-1)%mod+mod*2)%mod*p[i-2]%mod*p[n-i-1]%mod*f[i-2]%mod);
cout<<ans;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 19ms
memory: 16880kb
input:
7 3 7
output:
20640
result:
ok single line: '20640'
Test #2:
score: 5
Accepted
time: 23ms
memory: 16880kb
input:
7 2 6
output:
10560
result:
ok single line: '10560'
Test #3:
score: 5
Accepted
time: 31ms
memory: 16880kb
input:
178 88 176
output:
263756452
result:
ok single line: '263756452'
Test #4:
score: 5
Accepted
time: 24ms
memory: 16884kb
input:
165 64 151
output:
675678116
result:
ok single line: '675678116'
Test #5:
score: 5
Accepted
time: 33ms
memory: 16884kb
input:
188 83 184
output:
69478022
result:
ok single line: '69478022'
Test #6:
score: 5
Accepted
time: 25ms
memory: 16884kb
input:
158 62 144
output:
203749473
result:
ok single line: '203749473'
Test #7:
score: 5
Accepted
time: 26ms
memory: 16892kb
input:
1974 459 1845
output:
535987457
result:
ok single line: '535987457'
Test #8:
score: 5
Accepted
time: 23ms
memory: 16892kb
input:
1970 499 1944
output:
118089661
result:
ok single line: '118089661'
Test #9:
score: 5
Accepted
time: 27ms
memory: 16888kb
input:
1962 195 1766
output:
563043519
result:
ok single line: '563043519'
Test #10:
score: 5
Accepted
time: 28ms
memory: 16892kb
input:
1957 408 1858
output:
368025374
result:
ok single line: '368025374'
Test #11:
score: 5
Accepted
time: 84ms
memory: 20784kb
input:
999966 2907 1
output:
891313743
result:
ok single line: '891313743'
Test #12:
score: 5
Accepted
time: 101ms
memory: 20784kb
input:
999997 4828 2
output:
815004193
result:
ok single line: '815004193'
Test #13:
score: 5
Accepted
time: 104ms
memory: 20788kb
input:
999959 5271 2
output:
600125008
result:
ok single line: '600125008'
Test #14:
score: 5
Accepted
time: 106ms
memory: 20784kb
input:
999961 24134 10
output:
784444417
result:
ok single line: '784444417'
Test #15:
score: 5
Accepted
time: 106ms
memory: 20788kb
input:
999983 33966 10
output:
744109998
result:
ok single line: '744109998'
Test #16:
score: 5
Accepted
time: 76ms
memory: 20788kb
input:
999951 31503 999934
output:
518818294
result:
ok single line: '518818294'
Test #17:
score: 5
Accepted
time: 85ms
memory: 20784kb
input:
999953 21775 999941
output:
459927485
result:
ok single line: '459927485'
Test #18:
score: 5
Accepted
time: 78ms
memory: 20784kb
input:
999970 7889 999782
output:
979137112
result:
ok single line: '979137112'
Test #19:
score: 5
Accepted
time: 83ms
memory: 20788kb
input:
999972 6809 999964
output:
64469239
result:
ok single line: '64469239'
Test #20:
score: 5
Accepted
time: 82ms
memory: 20784kb
input:
999952 29898 999948
output:
801924273
result:
ok single line: '801924273'
Extra Test:
score: 0
Extra Test Passed