ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138786 | #239. count | gzhhtao | 0 | 0ms | 0kb | C++ | 1014b | 2021-10-02 10:22:52 | 2021-10-02 10:22:53 |
answer
#include<iostream>
using namespace std;
const long long mod=998244353;
long long n,m,k,xx,yy,fc[10000010],iv[10000010],ans;
long long pw(long long x){
long long ans=1;
for(long long i=mod-2;i;i>>=1,x=x*x%mod){
if(i&1){
ans=ans*x%mod;
}
}
return ans;
}
long long C(long long x,long long y){
if(x<xx){
return iv[y]*iv[x-y]%mod*fc[x]%mod;
}
long long ans=iv[y];
for(long long i=0;i<y;i++){
ans=(x-i)%mod*ans%mod;
}
return ans;
}
long long F(long long x){
if(x<0){
return 0;
}
long long ans=0,y;
for(long long i=0;i<=k;i++){
y=C(k,i)*C(x-i*(m-1)+k-1,k-1)%mod;
ans=(ans+(i&1?mod-1:1)*y%mod)%mod;
}
return ans;
}
int main(){
cin>>n>>m>>k;
xx=k*m;yy=n%m;
if(!m){
cout<<"0";
return 0;
}
fc[0]=1;
for(long long i=1;i<=n;i++){
fc[i]=fc[i-1]*i%mod;
}
iv[n]=pw(fc[n]);
for(long long i=n;i>=1;i--){
iv[i-1]=iv[i]*i%mod;
}
for(long long i=0;i<=k;i++){
ans=(ans+F(i*m+yy-k)*C((n-yy)/m-i+k-1,k-1)%mod)%mod;
}
cout<<ans;
}
Details
小提示:点击横条可展开更详细的信息
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