题目描述

 

原题来自：USACO 2009 Feb. Silver

牡 mǔ，畜父也。牝 pìn，畜母也。 ——《说文解字》

约翰要带 N 只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 K 只牝牛。

请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 5000011 取模。

思路：

 

DP 做法 ，f[i] 表示第i头牛为牡牛的方案数．

sum[i]=f[1]+f[2]+...+f[i].

f[i]=sum[i-k-1]+1.

统计答案:ans+=f[i] 

记录每头牛为牡牛的方案数即可，不只是统计f[n]---->f[n-k]的方案数

，

因为这样忽略了n--->n-k头牛中没有牡牛的情况。

#include
      
       #define ll long long #define R registerusing namespace std;const int N=100005;const int mod=5000011;int n,k,f[N],sum[N],ans,se=0;int main(){    scanf("%d%d",&n,&k);//第i头牛是　能　的方案数    for(R int i=1;i<=n;i++)    {        if(i-k-1>=1)        f[i]=(sum[i-k-1]+1)%mod;        else f[i]=1;        sum[i]=(sum[i-1]+f[i])%mod;        ans=(ans+f[i])%mod;    }    printf("%d",(ans+1)%mod);      return 0;}
      

 

组合做法：

枚举i头牡牛,则(i-1)*k头牝牛是固定不变的。接下来就考虑　i 头牡牛　和剩余牝牛　的不全相异元素的全排列

假设n个球，n_1个球相同,n_2个球相同,----,n_m个球相同,排列数为：

n!/(n_1!*n_2!...*n_m!)

#include
      
       #define ll long long #define R registerusing namespace std;const int N=1e6+1e5;const int mod=5000011;int n,k;ll ans=0,fac[N],inv[10000005];inline ll ksm(R ll x,R ll p){    R ll tot=1;    while(p)    {        if(p&1)        {        tot=(tot*x)%mod;        }        x=(x*x)%mod;        p>>=1;    }    return tot%mod;}int main(){    scanf("%d%d",&n,&k);    fac[0]=fac[1]=1;    for(R int i=2;i<=n+k+1;i++)    {        fac[i]=(fac[i-1]*i)%mod;    }    for(R int i=0;((i-1)*k+i)<=n;i++)    {        ans=(ans+(fac[n-(i-1)*k]*ksm((fac[i]*fac[(n-(i-1)*k-i)])%mod,mod-2)%mod)%mod)%mod;    }    printf("%lld",ans);      return 0;}