ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203187 | #3546. count | sjc061031 | 100 | 3832ms | 65352kb | C++11 | 2.4kb | 2024-02-20 10:46:29 | 2024-02-20 13:44:12 |
answer
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
int r[4000010],w[4000010];
int pw[2000010],rev[2000010],rr[2000010];
inline void add1(int &x,int y)
{
x+=y;
if(x>=MOD) x-=MOD;
}
inline void add2(int &x,int y)
{
x+=y;
if(x<0) x+=MOD;
}
inline int my_pow(int x,int y)
{
if(y==0) return 1;
if(y==1) return x;
int res=my_pow(x,y/2);
if(y%2==0) return 1ll*res*res%MOD;
else return 1ll*res*res%MOD*x%MOD;
}
inline int calc(int x,int y)
{
if(x<y) return 0;
return 1ll*pw[x]*rev[y]%MOD*rev[x-y]%MOD;
}
inline void init()
{
for(int i=1;i<22;i++){
int wn=my_pow(3,(MOD-1)/(1<<i)),now=1;
for(int j=0;j<(1<<(i-1));j++){
w[(1<<(i-1))+j]=now;
now=1ll*now*wn%MOD;
}
}
}
inline void NTT(vector<int> &a)
{
int n=(int)a.size();
int p=1,k=0;
while(p<n) p*=2,k++;
for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(k-1));
for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1;i<=k;i++){
for(int j=0;j<(1<<k);j+=(1<<i)){
int off=(1<<(i-1));
for(int l=j;l<j+off;l++){
int x=a[l],y=1ll*a[l+off]*w[off+l-j]%MOD;
a[l]=(x+y>=MOD)?x+y-MOD:x+y;
a[l+off]=(x-y<0)?x-y+MOD:x-y;
}
}
}
}
inline vector<int> convolution(vector<int> a,vector<int> b)
{
int n=(int)a.size(),m=(int)b.size();
int k=1;
while(k<n+m) k*=2;
a.resize(k);b.resize(k);
NTT(a);NTT(b);
for(int i=0;i<k;i++) a[i]=1ll*a[i]*b[i]%MOD;
NTT(a);
reverse(a.begin()+1,a.end());
a.resize(n+m-1);
int rev=my_pow(k,MOD-2);
for(int i=0;i<n+m-1;i++) a[i]=1ll*a[i]*rev%MOD;
return a;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
init();
int n,k,x;cin>>n>>k>>x;
pw[0]=1;
for(int i=1;i<=2*n;i++) pw[i]=1ll*pw[i-1]*i%MOD;
rev[2*n]=my_pow(pw[2*n],MOD-2);
for(int i=2*n-1;i>=0;i--) rev[i]=1ll*rev[i+1]*(i+1)%MOD;
rr[1]=1;
for(int i=2;i<=2*n;i++) rr[i]=MOD-1ll*(MOD/i)*rr[MOD%i]%MOD;
if(k==1){
cout<<pw[n]<<'\n';
return 0;
}
int ans=0,sum=0;
add1(ans,pw[n-1]);
for(int i=2;i<=n;i++){
add1(sum,1ll*calc(i-1+k-2,k-2)*(i-1)%MOD);
int now=1ll*pw[n-i]*pw[i-2]%MOD*calc(n-x,i-1)%MOD;
add1(ans,1ll*now*sum%MOD);
}
vector<int> v1,v2,v3;
for(int i=1;i<=n;i++) v1.push_back(i-1);
for(int i=n;i>=2;i--) v2.push_back(rr[i-1]);
v3=convolution(v1,v2);
for(int i=0;i<=n-1;i++){
int cur=1ll*pw[n-1]*calc(i+k-2,k-2)%MOD;
cur=1ll*cur*v3[n-1-i]%MOD;
add1(ans,cur);
}
cout<<ans<<'\n';
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 11ms
memory: 9480kb
input:
7 3 7
output:
20640
result:
ok single line: '20640'
Test #2:
score: 5
Accepted
time: 14ms
memory: 9484kb
input:
7 2 6
output:
10560
result:
ok single line: '10560'
Test #3:
score: 5
Accepted
time: 14ms
memory: 9488kb
input:
178 88 176
output:
263756452
result:
ok single line: '263756452'
Test #4:
score: 5
Accepted
time: 10ms
memory: 9488kb
input:
165 64 151
output:
675678116
result:
ok single line: '675678116'
Test #5:
score: 5
Accepted
time: 11ms
memory: 9492kb
input:
188 83 184
output:
69478022
result:
ok single line: '69478022'
Test #6:
score: 5
Accepted
time: 8ms
memory: 9492kb
input:
158 62 144
output:
203749473
result:
ok single line: '203749473'
Test #7:
score: 5
Accepted
time: 5ms
memory: 9616kb
input:
1974 459 1845
output:
535987457
result:
ok single line: '535987457'
Test #8:
score: 5
Accepted
time: 5ms
memory: 9616kb
input:
1970 499 1944
output:
118089661
result:
ok single line: '118089661'
Test #9:
score: 5
Accepted
time: 10ms
memory: 9608kb
input:
1962 195 1766
output:
563043519
result:
ok single line: '563043519'
Test #10:
score: 5
Accepted
time: 15ms
memory: 9608kb
input:
1957 408 1858
output:
368025374
result:
ok single line: '368025374'
Test #11:
score: 5
Accepted
time: 379ms
memory: 65348kb
input:
999966 2907 1
output:
891313743
result:
ok single line: '891313743'
Test #12:
score: 5
Accepted
time: 375ms
memory: 65352kb
input:
999997 4828 2
output:
815004193
result:
ok single line: '815004193'
Test #13:
score: 5
Accepted
time: 387ms
memory: 65348kb
input:
999959 5271 2
output:
600125008
result:
ok single line: '600125008'
Test #14:
score: 5
Accepted
time: 397ms
memory: 65348kb
input:
999961 24134 10
output:
784444417
result:
ok single line: '784444417'
Test #15:
score: 5
Accepted
time: 384ms
memory: 65348kb
input:
999983 33966 10
output:
744109998
result:
ok single line: '744109998'
Test #16:
score: 5
Accepted
time: 375ms
memory: 65352kb
input:
999951 31503 999934
output:
518818294
result:
ok single line: '518818294'
Test #17:
score: 5
Accepted
time: 362ms
memory: 65348kb
input:
999953 21775 999941
output:
459927485
result:
ok single line: '459927485'
Test #18:
score: 5
Accepted
time: 365ms
memory: 65348kb
input:
999970 7889 999782
output:
979137112
result:
ok single line: '979137112'
Test #19:
score: 5
Accepted
time: 361ms
memory: 65352kb
input:
999972 6809 999964
output:
64469239
result:
ok single line: '64469239'
Test #20:
score: 5
Accepted
time: 344ms
memory: 65348kb
input:
999952 29898 999948
output:
801924273
result:
ok single line: '801924273'
Extra Test:
score: 0
Extra Test Passed