ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138781 | #239. count | johnson2007 | 100 | 5921ms | 157444kb | C++ | 1015b | 2021-10-02 10:09:57 | 2021-10-02 10:09:58 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7 + 5;
const ll mod=998244353;
ll add(ll a,ll b){ return (a+b)%mod;}
ll mul(ll a,ll b){ return (a*b)%mod;}
ll n,m,k,fac[N],inv[N];
ll C(ll n,ll m){
if(n<0||m<0||n<m) return 0;
if(n<N) return mul(fac[n],mul(inv[m],inv[n-m]));
else{
ll ret=inv[m];
for(ll i=n;i >= n-m + 1;i--) ret=mul(ret,i % mod);
return ret;
}
}
ll g(ll n,ll m){
if(n<0) return 0;
return C(n + m-1,m-1);
}
ll f(ll n,ll m,ll k){
n-=m;
if(n<0)return 0;
ll ans=0;
for(ll i=0;i<=m;i++){
ll ret=mul(g(n-i*k,m),C(m,i));
(i%2)?ans=add(ans,mod-ret):(ans=add(ans,ret));
}
return ans;
}
int main(){
cin>>n>>m>>k;
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(ll i=2;i<N;i++) fac[i]=mul(fac[i-1],i);
for(ll i=2;i<N;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
for(ll i=2;i<N;i++) inv[i]=mul(inv[i],inv[i-1]);
ll ans=0;
for(ll i=0;i<k;i++){
ans=add(ans,mul(f(i*m+n%m,k,m-1),g((n-n%m)/m-i,k)));
}
cout<<ans;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 536ms
memory: 157444kb
input:
1000 1000 3
output:
498501
result:
ok single line: '498501'
Test #2:
score: 10
Accepted
time: 601ms
memory: 157444kb
input:
2000 2000 2
output:
1999
result:
ok single line: '1999'
Test #3:
score: 10
Accepted
time: 592ms
memory: 157440kb
input:
1999 1005 3
output:
1992024
result:
ok single line: '1992024'
Test #4:
score: 10
Accepted
time: 568ms
memory: 157440kb
input:
523098578902387543 1990 3
output:
741828632
result:
ok single line: '741828632'
Test #5:
score: 10
Accepted
time: 516ms
memory: 157444kb
input:
985435493875384653 1987 3
output:
930955578
result:
ok single line: '930955578'
Test #6:
score: 10
Accepted
time: 578ms
memory: 157444kb
input:
854378965978354365 4898 20
output:
72755158
result:
ok single line: '72755158'
Test #7:
score: 10
Accepted
time: 547ms
memory: 157440kb
input:
869347685748976465 5000 20
output:
946187174
result:
ok single line: '946187174'
Test #8:
score: 10
Accepted
time: 654ms
memory: 157444kb
input:
985493567483653416 4999 2000
output:
715344547
result:
ok single line: '715344547'
Test #9:
score: 10
Accepted
time: 674ms
memory: 157444kb
input:
1000000000000000000 4987 1992
output:
142311097
result:
ok single line: '142311097'
Test #10:
score: 10
Accepted
time: 655ms
memory: 157444kb
input:
666666666623333333 4998 1999
output:
7913341
result:
ok single line: '7913341'