组合数的最后K位(全部后K位)

Question

组合数的最后K位谁会
本蒟蒻不会组合数，哪位巨佬帮看看
真的很感激

Answer 1

引自免费微信小程序：皆我百晓生

当然，为了获取组合数最后K位的值，我们需要用到模运算和快速幂算法。这里有一个C++代码示例来计算组合数C(n, m)的最后K位（假设K小于32，因为我们将使用32位整数进行计算）：

#include <iostream>
#include <vector>

using namespace std;

// 计算组合数 C(n, m) 的最后 K 位
vector<int> last_k_bits(int n, int m, int k) {
    if (m > n || k <= 0) return {};

    // 初始化模数和逆元数组
    vector<int> mods(1 << k, 1);
    for (int i = 1; i < (1 << k); ++i)
        mods[i] = mods[i - 1] * 10 % (1 << k);

    // 计算阶乘及其逆元
    vector<int> fact(1 << k), inv_fact(1 << k);
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i <= max(n, m); ++i) {
        fact[i] = fact[i - 1] * i % (1 << k);
        inv_fact[i] = inv_fact[i - 1] * mods[i] % (1 << k);
    }

    // 计算组合数并取模
    int comb = inv_fact[n] * inv_fact[m] % (1 << k);
    comb *= fact[n] % (1 << k);
    comb %= (1 << k);

    // 返回最后 K 位
    vector<int> result(k);
    for (int i = 0; i < k; ++i) {
        result[k - 1 - i] = comb & 1;
        comb >>= 1;
    }
    return result;
}

int main() {
    int n = 100, m = 50, k = 5;
    vector<int> last_bits = last_k_bits(n, m, k);
    
    // 输出最后 K 位
    for (int bit : last_bits) {
        cout << bit;
    }
    cout << endl;

    return 0;
}

这段代码首先初始化了模数数组以及阶乘及其逆元数组，并通过这些预计算的结果求解组合数 C(n, m) 对 (1 << k) 取模后的值。最后将结果转换为一个包含最后 K 位的整数数组。

请注意，由于计算过程中涉及到大整数的模运算和逆元计算，当n或m较大时，可能需要更高效的方法如中国剩余定理或者更高级的数论技巧。此外，本代码未处理k大于32的情况，若实际需求中k可能超过32位，请考虑使用大整数库或者其他解决方案。