题目

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
const int mod = 5000011;
int fac[N], infac[N];
int qmi(int base, int expo, int p)
{int retval = 1;while(expo){if(expo & 1) retval = (LL)retval * base % p;base = (LL)base * base % p;expo >>= 1;}return retval;
}
void init(int n)
{fac[0] = infac[0] = 1;for(int i = 1; i <= n; i++){fac[i] = (LL)fac[i-1] * i % mod;infac[i] = (LL)infac[i-1] * qmi(i, mod-2, mod) % mod;}
}
int getc(int a, int b)
{return (LL)fac[a] * infac[b] % mod * infac[a-b] % mod;
}
int main()
{int n, k;cin >> n >> k;init(N);int ans = 0;if(n == 1) ans = 2;else if(n == 2) ans = 2;else{ans += 1 + n;for(int i = 2; i + (i-1) * k <= n; i++){int j = n - i - (i-1) * k;if(j == 0) ans += 1;else ans += getc(i+j, j);ans %= mod;}}cout << ans;return 0;
}

思路

（牡牛数目用A表示，牝牛数目用B表示）

遍历A数目从0~n。

其中，当A=0时，方案数为1。

当A = 1时，方案数为n。

当A >= 2时，假设有ABA结构(多余的B先不考虑)：其中A = i，B = (i-1) * k。

则剩余的B数量为j。

若此时j == 0，则方案数为1。（getc中i >= 2, j+1 = 1，retval = 0）。

若j != 0，B牛有j个，存在i+1个空。

这下最麻烦的部分就是如何把B牛分到i+1个位置里，位置可以放0个。

1        n球(牛)同 m盒子不同 盒子不空

C(n-1, m-1)

2        如果改成盒子可空，则等价于：加入m个透明假球 仍旧盒子不空

C(n+m-1, m-1)。其中全是透明假球的盒子就等价于空盒子，m个的目的是为了产生m-1个空盒子的情况。