ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138779 | #239. count | johnson2007 | 10 | 5832ms | 157444kb | C++ | 956b | 2021-10-02 10:08:33 | 2021-10-02 10:08:33 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7+5;
const ll mod=998244353;
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(fac[n]*(inv[m]*inv[n-m])%mod)%mod;
else{
ll ret=inv[m];
for(ll i=n;i>=n-m+1;i--)ret=(ret*(i%mod))%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=(g(n-i*k,m)*C(m,i))%mod;
ans=(i%2)?(ans-ret+mod)%mod:(ans+ret)%mod;//容斥
}
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]=(fac[i-1]*i)%mod;
for(ll i=2;i<N;i++)inv[i]=((mod-mod/i)*inv[mod%i])%mod;
for(ll i=2;i<N;i++)inv[i]=(inv[i]*inv[i-1])%mod;
//小于m
ll ans=0;
for(ll i=0;i<k;i++)
ans=(ans+(f(i*m+n%m,k,m-1)*g((n-n%m)/m-i,k))%mod)%mod;
cout<<ans;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 505ms
memory: 157440kb
input:
1000 1000 3
output:
103261800
result:
wrong answer 1st lines differ - expected: '498501', found: '103261800'
Test #2:
score: 10
Accepted
time: 561ms
memory: 157444kb
input:
2000 2000 2
output:
1999
result:
ok single line: '1999'
Test #3:
score: 0
Wrong Answer
time: 590ms
memory: 157440kb
input:
1999 1005 3
output:
857607642
result:
wrong answer 1st lines differ - expected: '1992024', found: '857607642'
Test #4:
score: 0
Wrong Answer
time: 536ms
memory: 157444kb
input:
523098578902387543 1990 3
output:
573830341
result:
wrong answer 1st lines differ - expected: '741828632', found: '573830341'
Test #5:
score: 0
Wrong Answer
time: 563ms
memory: 157440kb
input:
985435493875384653 1987 3
output:
455923951
result:
wrong answer 1st lines differ - expected: '930955578', found: '455923951'
Test #6:
score: 0
Wrong Answer
time: 590ms
memory: 157444kb
input:
854378965978354365 4898 20
output:
902687568
result:
wrong answer 1st lines differ - expected: '72755158', found: '902687568'
Test #7:
score: 0
Wrong Answer
time: 535ms
memory: 157440kb
input:
869347685748976465 5000 20
output:
935573213
result:
wrong answer 1st lines differ - expected: '946187174', found: '935573213'
Test #8:
score: 0
Wrong Answer
time: 634ms
memory: 157440kb
input:
985493567483653416 4999 2000
output:
362063712
result:
wrong answer 1st lines differ - expected: '715344547', found: '362063712'
Test #9:
score: 0
Wrong Answer
time: 640ms
memory: 157444kb
input:
1000000000000000000 4987 1992
output:
587270423
result:
wrong answer 1st lines differ - expected: '142311097', found: '587270423'
Test #10:
score: 0
Wrong Answer
time: 678ms
memory: 157440kb
input:
666666666623333333 4998 1999
output:
674398615
result:
wrong answer 1st lines differ - expected: '7913341', found: '674398615'