约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛．牛们要站成一排．但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛．
请计算一共有多少种排队的方法．所有牡牛可以看成是相同的，所有牝牛也一样．答案对5000011取模
/* 排列组合问题 枚举杜牛的数量，然后从n中删去至少需要添加的牝牛的数量，然后在安排杜牛即可。 ans=ΣC(n-(i-1)*k,i) */ #include<cstdio> #include<iostream> #define mod 5000011 #define lon long long using namespace std; int n,k;lon ans; lon ksm(lon a,lon b){ lon base=a,r=1; while(b){ if(b&1) r*=base; base*=base; r%=mod; base%=mod; b>>=1; } return r; } lon C(int n,int m){ m=min(m,n-m);lon r1=1,r2=1; for(int i=n-m+1;i<=n;i++) r1=(r1*(lon)i)%mod; for(int i=1;i<=m;i++) r2=(r2*i)%mod; return (r1*ksm(r2,mod-2))%mod; } int main(){ scanf("%d%d",&n,&k); for(int i=0;i<=n;i++){ int t=n-(i-1)*k; if(t<i) break; ans=(ans+C(t,i))%mod; } cout<<ans; return 0; }
原文：http://www.cnblogs.com/harden/p/6286182.html