计算大n和k的二项式系数（nCk）

一尘不染

计算大n和k的二项式系数（nCk）

algorithm

我只是看到了这个问题，却不知道如何解决。您能给我提供算法，C ++代码或想法吗？

这是一个非常简单的问题。给定N和K的值，您需要告诉我们二项式系数C（N，K）的值。您可以放心，K <=
N，并且N的最大值是1,000,000,000,000,000。由于该值可能非常大，因此您需要以1009为模来计算结果。输入

输入的第一行包含测试用例T的数量，最多为1000。接下来的T行中的每一行都由两个以空格分隔的整数N和K组成，其中0 <= K <= N和1 <= N
<= 1,000,000,000,000,000 。输出量

对于每个测试用例，在新行上打印二项式系数C（N，K）以1009为模的值。

输入：
3
3 1
5 2
10 3

输出：
3
10
120

阅读 398

2020-07-28

共1个答案

一尘不染

注意1009是质数。

现在您可以使用卢卡斯定理。

哪个状态：

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.

这样，您的问题就减少了，可以找到最多为a的选择b形式为a <= 1009和b <= 1009的对数N / log
1009数字（以1009为基的N的位数）的乘积1009。

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

注意：

对于N = 10 ^ 15，N选择N / 2大于2 ^（100000000000000），这远远超出了无符号长整型。

同样，卢卡斯定理建议的算法为O（log N），这 exponentially比尝试直接计算二项式系数要快（即使您做了mod
1009来处理溢出问题）。

这是我很久以前写的关于二项式的一些代码，您需要做的就是对其进行修改，以进行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;
}

2020-07-28