铜c-组合数学

可以用组合数学来做，一开始想复杂了

• 利用隔板法求所有结果
• 最终的公式：

• m = 0, 1时要特判，当时无方案数

ac代码

using ll = long long;
void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if (!b) {
        g = a, x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, g, y, x);
    y -= x * (a / b);
}

// ax=1(mod m)
ll inverse(ll a, ll m) {//扩展欧几里得法求逆元，返回-1代表没有逆元
    ll g, x, y;
    exgcd(a, m, g, x, y);
    return g == 1 ? (x % m + m) % m : -1;
}

#define mod(x) ((x) % _mod)
const ll _mod = 1000000007;
const int M = 2e3 + 10;
ll f[M*M];
/*****************************************************************************/
class Solution {
public:
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        if ((m - 1) * k + m > n) return 0;
        if (m == 0) return 1;
        if (m == 1) return n - 1;
        f[0] = f[1] = 1;
        for (ll i = 2; i < M * M; ++i) f[i] = mod(f[i - 1] * i);
        ll ans = 0;
        for (ll i = (m - 1) * k; i <= n - m; ++i) {
            int indx1 = i - (m - 1) * k + m - 2, indx2 = indx1 - m + 2;
            ll d = n - m - i + 1;
            ll sum =  mod(f[indx1] * inverse(mod(f[m - 2] * f[indx2]), _mod));
            sum = mod(sum * d);
            ans = mod(ans + sum);
        }
        return mod(ans);
    }
};
/*****************************************************************************/