关于#c++#的问题：每个盒子最多放K个球请计算将这N个球全部放入盒子中的方案数模1000007后的结果

Question

有N个相同的球，M个不同的盒子，每个盒子最多放K个球
请计算将这N个球全部放入盒子中的方案数模1000007后的结果

时间限制：10000
内存限制：131072
输入
三个正整数，依次为N，M，K

输出
输出方案数模1000007后的结果

样例输入
4 2 3
样例输出
3
提示
总共有3种方案，依次为 { 3 ， 1 }，{ 2 ， 2 }，{ 1 ， 3 }。 对于100%的数据， N，M ≤ 5000

Answer 1

该回答引用ChatGPT

如有疑问，可以回复我！

请测试

#include <iostream>
#include <vector>

const int MOD = 1000007;

int fast_pow(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (1LL * result * base) % mod;
        }
        base = (1LL * base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    int N, M, K;
    std::cin >> N >> M >> K;

    std::vector<int> factorial(10005, 1);
    for (int i = 1; i <= 10000; ++i) {
        factorial[i] = (1LL * factorial[i - 1] * i) % MOD;
    }

    if (K == 1) {
        std::cout << fast_pow(M, N, MOD) << std::endl;
        return 0;
    }

    int ans = 0;
    for (int i = 0; i * K <= N && i <= M; ++i) {
        int temp = (1LL * factorial[N - i] * fast_pow(factorial[K - 1], M, MOD)) % MOD;
        temp = (1LL * temp * fast_pow(factorial[K * i], MOD - 2, MOD)) % MOD;
        temp = (1LL * temp * fast_pow(factorial[M], MOD - 2, MOD)) % MOD;
        temp = (1LL * temp * fast_pow(factorial[M - i], MOD - 2, MOD)) % MOD;
        ans = (ans + temp) % MOD;
    }

    std::cout << ans << std::endl;

    return 0;
}