ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#148190 | #239. count | chsuhan | 30 | 48ms | 2752kb | C++11 | 1.2kb | 2022-04-16 14:43:23 | 2022-04-16 14:43:24 |
answer
#include<bits/stdc++.h>
#define ll long long
#define inf 1e9
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define per(i,r,l) for(register int i=r;i>=l;--i)
using namespace std;
const int N=1e5+10,Mod=998244353;
ll n,m,k;
ll jc[N],jc_inv[N];
ll ans,lim;
inline ll ksm(ll a,ll b){
ll ret=1;
while (b){
if(b&1)ret=ret*a%Mod;
a=a*a%Mod;
b>>=1;
}
return ret%Mod;
}
inline void init(){
jc[0]=jc_inv[0]=1;
rep(i,1,100000){
jc[i]=jc[i-1]*i%Mod;
jc_inv[i]=ksm(jc[i],Mod-2);
}
//rep(i,1,10)cout<<jc_inv[i]<<' ';cout<<endl;
}
inline ll C(ll n,ll m){
if(n<0||m<0||n<m)return 0;
if(n<=1e5)return jc[n]*jc_inv[m]%Mod*jc_inv[n-m]%Mod;
else{
ll ret=jc_inv[m];
rep(i,n-m+1,n)ret=ret*i%Mod;
return ret;
}
}
inline ll g(ll n,ll m){
if(n<0)return 0;
return C(n+m-1,m-1);
}
inline ll f(ll n,ll m,ll k){
n-=m;
if(n<0)return 0;
ll ret=0;
rep(i,0,m){
ll w=(i&1)?-1:1;
ret=(ret+w*g(n-i*k,m)*C(m,i)%Mod)%Mod;
ret=(ret+Mod)%Mod;
}
return ret;
}
int main(){
init();
scanf("%lld%lld%lld",&n,&m,&k);
lim=n%m;
rep(i,0,k-1)ans=(ans+f(i*m+lim,k,m-1)*g((n-lim)/m-i,k)%Mod)%Mod;
printf("%lld\n",ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 14ms
memory: 2748kb
input:
1000 1000 3
output:
498501
result:
ok single line: '498501'
Test #2:
score: 10
Accepted
time: 17ms
memory: 2748kb
input:
2000 2000 2
output:
1999
result:
ok single line: '1999'
Test #3:
score: 10
Accepted
time: 17ms
memory: 2752kb
input:
1999 1005 3
output:
1992024
result:
ok single line: '1992024'
Test #4:
score: 0
Time Limit Exceeded
input:
523098578902387543 1990 3
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
985435493875384653 1987 3
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
854378965978354365 4898 20
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
869347685748976465 5000 20
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
985493567483653416 4999 2000
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
1000000000000000000 4987 1992
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
666666666623333333 4998 1999