3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 243 Solved: 167
[Submit][Status][Discuss]
Description
约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛.牛们要站成一排.但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛.
请计算一共有多少种排队的方法.所有牡牛可以看成是相同的,所有牝牛也一样.答案对5000011取模
Input
一行,输入两个整数N和K.
Output
一个整数,表示排队的方法数.
Sample Input
4 2
Sample Output
6
样例说明
6种方法分别是:牝牝牝牝,牡牝牝牝,牝牡牝牝,牝牝牡牝,牝牝牝牡,牡牝牝牡
样例说明
6种方法分别是:牝牝牝牝,牡牝牝牝,牝牡牝牝,牝牝牡牝,牝牝牝牡,牡牝牝牡
HINT
Source
/*
以下牡牛为a,牝牛为b。
学完排列计数后试着来写这题,“至少”一词可以给我们提示,我们可以枚举a为x头(x>1),然后算出对应的排列累计起来。
对于x头a,首先我们先缩掉必要的k头牛(x-1)*k,然后这时可以特判可以先结束(因为单调的),然后在缩好后的x个点和n-x-(x-1)*k个点进行多重排列就行了。
逆元:a^(phi(n)-1) mod n
*/
#include<cstdio>
#include<iostream>
using namespace std;
const int mod=;
typedef long long ll;
int n,k;ll ans;
ll fpow(ll a,ll p){
ll res=;
for(;p;p>>=,a=a*a%mod) if(p&) res=res*a%mod;
return res;
}
ll C(ll n,ll m){
m=min(m,n-m);ll r1=,r2=;
for(ll i=n-m+;i<=n;i++) r1=r1*i%mod;
for(ll i=;i<=m;i++) r2=r2*i%mod;
return r1*fpow(r2,mod-);
}
int main(){
scanf("%d%d",&n,&k);
for(ll i=;i<=n;i++){
ll t=n-(i-)*k;
if(t<i) break;
ans=(ans+C(t,i))%mod;
}
cout<<ans;
return ;
}
/*
DP:
设 f[i]表示取的最后一个数是i的方案数
则 f[i]=siama(f[j]) i-j>k
*/
#include<cstdio>
#define mod 5000011
using namespace std;
int n,k,f[(int)1e5+];
int main(){
scanf("%d%d",&n,&k);
f[]=;
int sum=,ans=;
for(int i=;i<=n;i++){
if(i>k+) sum=(sum+f[i-k-])%mod;
f[i]=sum;
ans=(ans+f[i])%mod;
}
printf("%d\n",ans);
return ;
}