ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138792 | #239. count | gzhhtao | 0 | 0ms | 0kb | C++11 | 1.0kb | 2021-10-02 10:30:36 | 2021-10-02 10:30:37 |
answer
#include<iostream>
using namespace std;
const int mod=998244353;
long long n;
int m,k,xx,yy,fc[10000010],iv[10000010],ans;
int mul(int x,int y){
return 1ll*x*y%mod;
}
void add(int& x,int y){
if((x+=y)>=mod){
x-=mod;
}
}
int pw(int x,int i=mod-2){
int ans=1;
for(;i;i>>=1,x=mul(x,x)){
if(i&1){
ans=mul(ans,x);
}
}
return ans;
}
int C(long long x,int y){
if(x<xx){
return mul(fc[x],mul(iv[y],iv[x-y]));
}
int ans=iv[y];
for(int i=0;i<y;i++){
ans=mul(ans,(x-i)%mod);
}
return ans;
}
int F(int x){
if(x<0){
return 0;
}
int ans=0,y;
for(int i=0;i<=k;i++){
y=mul(C(k,i),C(x-i*(m-1)+k-1,k-1));
add(ans,mul((i&1?mod-1:1),y));
}
return ans;
}
int main(){
cin>>n>>m>>k;
xx=k*m;yy=n%m;
if(!m){
cout<<"0";
return 0;
}
fc[0]=1;
for(int i=1;i<=n;i++){
fc[i]=mul(fc[i-1],i);
}
iv[n]=pw(fc[n]);
for(int i=n;i>=1;i--){
iv[i-1]=mul(iv[i],i);
}
for(int i=0;i<=k;i++){
add(ans,mul(F(i*m+yy-k),C((n-yy)/m-i+k-1,k-1)));
}
cout<<ans;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Runtime Error
input:
1000 1000 3
output:
result:
Test #2:
score: 0
Runtime Error
input:
2000 2000 2
output:
result:
Test #3:
score: 0
Runtime Error
input:
1999 1005 3
output:
result:
Test #4:
score: 0
Runtime Error
input:
523098578902387543 1990 3
output:
result:
Test #5:
score: 0
Runtime Error
input:
985435493875384653 1987 3
output:
result:
Test #6:
score: 0
Runtime Error
input:
854378965978354365 4898 20
output:
result:
Test #7:
score: 0
Runtime Error
input:
869347685748976465 5000 20
output:
result:
Test #8:
score: 0
Runtime Error
input:
985493567483653416 4999 2000
output:
result:
Test #9:
score: 0
Runtime Error
input:
1000000000000000000 4987 1992
output:
result:
Test #10:
score: 0
Runtime Error
input:
666666666623333333 4998 1999