ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138826 | #239. count | gzhhtao | 100 | 2975ms | 79332kb | C++11 | 1.0kb | 2021-10-02 11:38:33 | 2021-10-02 11:38:34 |
answer
#include<iostream>
using namespace std;
const int N=10000010,mod=998244353;
long long n;
int m,k,fc[N],iv[N],ans;
int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int C(long long x,int y){
if(x<0||y<0||x<y){
return 0;
}
if(x<N){
return mul(fc[x],mul(iv[y],iv[x-y]));
}
int ans=iv[y];
for(long long i=x;i>=x-y+1;i--){
ans=mul(ans,i%mod);
}
return ans;
}
int G(long long x,int y){
if(x<0)return 0;
return C(x+y-1,y-1);
}
int F(int x,int y,int z){
x-=y;
if(x<0){
return 0;
}
int ans=0;
for(int i=0;i<=y;i++){
int res=mul(G(x-i*z,y),C(y,i));
ans=(i&1)?add(ans,mod-res):add(ans,res);
}
return ans;
}
int main(){
cin>>n>>m>>k;
fc[0]=fc[1]=iv[0]=iv[1]=1;
for(int i=2;i<N;i++){
fc[i]=mul(fc[i-1],i);
}
for(int i=2;i<N;i++){
iv[i]=mul(mod-mod/i,iv[mod%i]);
}
for(int i=2;i<N;i++){
iv[i]=mul(iv[i],iv[i-1]);
}
long long r=n%m;
for(int i=0;i<k;i++){
ans=add(ans,mul(F(i*m+r,k,m-1),G((n-r)/m-i,k)));
}
cout<<ans;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 260ms
memory: 79328kb
input:
1000 1000 3
output:
498501
result:
ok single line: '498501'
Test #2:
score: 10
Accepted
time: 244ms
memory: 79328kb
input:
2000 2000 2
output:
1999
result:
ok single line: '1999'
Test #3:
score: 10
Accepted
time: 263ms
memory: 79328kb
input:
1999 1005 3
output:
1992024
result:
ok single line: '1992024'
Test #4:
score: 10
Accepted
time: 262ms
memory: 79328kb
input:
523098578902387543 1990 3
output:
741828632
result:
ok single line: '741828632'
Test #5:
score: 10
Accepted
time: 297ms
memory: 79328kb
input:
985435493875384653 1987 3
output:
930955578
result:
ok single line: '930955578'
Test #6:
score: 10
Accepted
time: 260ms
memory: 79328kb
input:
854378965978354365 4898 20
output:
72755158
result:
ok single line: '72755158'
Test #7:
score: 10
Accepted
time: 265ms
memory: 79328kb
input:
869347685748976465 5000 20
output:
946187174
result:
ok single line: '946187174'
Test #8:
score: 10
Accepted
time: 365ms
memory: 79328kb
input:
985493567483653416 4999 2000
output:
715344547
result:
ok single line: '715344547'
Test #9:
score: 10
Accepted
time: 388ms
memory: 79328kb
input:
1000000000000000000 4987 1992
output:
142311097
result:
ok single line: '142311097'
Test #10:
score: 10
Accepted
time: 371ms
memory: 79332kb
input:
666666666623333333 4998 1999
output:
7913341
result:
ok single line: '7913341'