3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 243  Solved: 167

[][][]

Description

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

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

Input

    一行，输入两个整数N和K.

Output

 

    一个整数，表示排队的方法数．

Sample Input

4 2

Sample Output

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
      
       #include
       
        using namespace std;const int mod=5000011;typedef long long ll;int n,k;ll ans;ll fpow(ll a,ll p){    ll res=1;    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;    return res;}ll C(ll n,ll m){    m=min(m,n-m);ll r1=1,r2=1;    for(ll i=n-m+1;i<=n;i++) r1=r1*i%mod;    for(ll i=1;i<=m;i++) r2=r2*i%mod;    return r1*fpow(r2,mod-2);}int main(){    scanf("%d%d",&n,&k);    for(ll i=0;i<=n;i++){        ll t=n-(i-1)*k;        if(t
       
      

 

/*DP:设 f[i]表示取的最后一个数是i的方案数则 f[i]=siama(f[j]) i-j>k*/#include
      
       #define mod 5000011using namespace std;int n,k,f[(int)1e5+5];int main(){    scanf("%d%d",&n,&k);    f[0]=1;    int sum=1,ans=1;    for(int i=1;i<=n;i++){         if(i>k+1) sum=(sum+f[i-k-1])%mod;         f[i]=sum;         ans=(ans+f[i])%mod;    }    printf("%d\n",ans);     return 0;}