题目描述

n头牛排成一队，求任意两只牡牛之间至少要有 K 只牝牛的队形的方案数

样例

4 2
6

算法 （非DP的组合计数法）

可以用牡牛的数量进行分类：0,1,2,3......
0头牡牛的方案数：1
1头牡牛的方案数：n
2头牡牛的方案数：先移去k头牝牛，然后在剩下的牛中任选两头作为牡牛，可以假想成在选中的两头牡牛中插入k头牝牛
3头牡牛的方案数：类似2头牡牛
…
以此类推

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
const ll mod = 5000011;

ll fact[N], infact[N];
ll qmi(ll a, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int main() {

    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2) % mod;
    }

    ll n, k;
    scanf("%lld%lld", &n, &k);
    ll res = 1 + n;
    for (ll i = 1; i * k + i + 1 <= n; ++i) {
        ll x = i + 1, y = n - i * k;
        res = (res + (fact[y] * infact[y - x] % mod * infact[x] % mod)) % mod;
    }
    printf("%lld", res);
    return 0;
}