c++ - 计算大 n 和 k 的二项式系数 (nCk)

Question

我刚看到这个问题，不知道如何解决。你能给我提供算法、C++代码或想法吗？

This is a very simple problem. Given the value of N and K, you need to tell us the value of the binomial coefficient C(N,K). You may rest assured that K <= N and the maximum value of N is 1,000,000,000,000,000. Since the value may be very large, you need to compute the result modulo 1009. Input

The first line of the input contains the number of test cases T, at most 1000. Each of the next T lines consists of two space separated integers N and K, where 0 <= K <= N and 1 <= N <= 1,000,000,000,000,000. Output

For each test case, print on a new line, the value of the binomial coefficient C(N,K) modulo 1009. Example

Input:
3
3 1
5 2
10 3

Output:
3
10
120

Answer 1

注意 1009 是素数。

现在您可以使用 Lucas' Theorem .

其中规定:

Let p be a prime.
If n  = a1a2...ar when written in base p and
if k  = b1b2...br when written in base p

(pad with zeroes if required)

Then

(n choose k) modulo p = (a1 choose b1) * (a2 choose  b2) * ... * (ar choose br) modulo p.

i.e. remainder of n choose k when divided by p is same as the remainder of
the product (a1 choose b1) * .... * (ar choose br) when divided by p.
Note: if bi > ai then ai choose bi is 0.

因此，您的问题被简化为找到最多 log N/log 1009 个数字(以 1009 为底的 N 的位数)的乘积模 1009，形式为 a 选择 b，其中 a <= 1009 和 b <= 1009。

即使 N 接近 10^15，这也应该更容易。

Note:

For N=10^15, N choose N/2 is more than 2^(100000000000000) which is way beyond an unsigned long long.

Also, the algorithm suggested by Lucas' theorem is O(log N) which is exponentially faster than trying to compute the binomial coefficient directly (even if you did a mod 1009 to take care of the overflow issue).

这是我很久以前写的一些 Binomial 代码，你需要做的就是修改它来做模 1009 的运算(可能有错误，不一定推荐的编码风格):

class Binomial
{
public:
    Binomial(int Max)
    {
        max = Max+1;
        table = new unsigned int * [max]();
        for (int i=0; i < max; i++)
        {
            table[i] = new unsigned int[max]();

            for (int j = 0; j < max; j++)
            {
                table[i][j] = 0;
            }
        }
    }

    ~Binomial()
    {
        for (int i =0; i < max; i++)
        {
            delete table[i];
        }
        delete table;
    }

    unsigned int Choose(unsigned int n, unsigned int k);

private:
    bool Contains(unsigned int n, unsigned int k);

    int max;
    unsigned int **table;
};

unsigned int Binomial::Choose(unsigned int n, unsigned int k)
{
    if (n < k) return 0;
    if (k == 0 || n==1 ) return 1;
    if (n==2 && k==1) return 2;
    if (n==2 && k==2) return 1;
    if (n==k) return 1;


    if (Contains(n,k))
    {
        return table[n][k];
    }
    table[n][k] = Choose(n-1,k) + Choose(n-1,k-1);
    return table[n][k];
}

bool Binomial::Contains(unsigned int n, unsigned int k)
{
    if (table[n][k] == 0) 
    {
        return false;
    }
    return true;
}