计算大n&k的二项式系数(nCk)

Question

我刚刚看到这个问题而不知道如何解决它.你可以请我提供算法,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

Answer 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.

因此,您的问题被简化为找到格式为1009的最多log N/log 1009数字(基数1009中N的位数)的形式a选择b,其中a <= 1009且b <= 1009.

即使N接近10 ^ 15,这也应该更容易.

注意:

对于N = 10 ^ 15,N选择N/2大于2 ^(100000000000000),这超出了无符号长long.

此外,卢卡斯定理建议的算法是O(log N),它 exponentially比直接计算二项式系数更快(即使你做了一个mod 1009来处理溢出问题).

这里有一些我很久以前写的二项式代码,所有你需要做的就是修改它来做模1009的操作(可能有bug,不一定推荐编码风格):

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;
}

Answer 2

二项式系数是一个因子除以另外两个因子,尽管k!底部的术语以明显的方式取消.

观察如果1009(包括它的倍数)在分子中出现的次数多于分母,那么答案mod 1009为0.在分母中出现的次数不能超过分子(因为二项式系数是整数)因此,你必须做任何事情的唯一情况是它们在两者中出现的次数相同.不要忘记将(1009)^ 2的倍数计算为两个,依此类推.

在那之后,我认为你只是在清理小案例(意味着少量的值乘以/除以),虽然我不确定没有几个测试.在正面1009是素数,因此算术模1009在一个场中发生,这意味着在从顶部和底部输出1009的倍数之后,你可以按任何顺序完成乘法和除法mod 1009的其余部分.

如果剩下非小的情况,它们仍然会将长连续的整数相乘.这可以通过了解来简化1008! (mod 1009).它是-1(如果你愿意,则为1008),因为1 ... 1008是p-1素数域的非零元素p.因此它们由1,-1组成,然后(p-3)/2是乘法反转对.

因此,例如考虑C((1009 ^ 3),200)的情况.

想象一下,1009的数量是相等的(不知道它们是否是,因为我没有编写公式来找出),所以这是一个需要工作的情况.

在顶部我们有201 ... 1008,我们必须计算或查找预先计算的表,然后1009,然后1010 ... 2017年,2018年,2019年...... 3026年,3027年等. ..范围都是-1,所以我们只需知道有多少这样的范围.

留下1009,2018,3027,一旦我们用1009从底部取消它们将只是1,2,3,...... 1008,1010,......再加上1009 ^ 2的倍数,这再次我们将取消并使用连续的整数来增加.

我们可以做一些与底部非常相似的东西来计算产品mod 1009的"1 ... 1009 ^ 3 - 200,其中1009的所有功率被分开".这使我们在一个主要领域中分裂.IIRC原则上很棘手,但1009是一个足够小的数字,我们可以管理其中的1000个(测试用例数量的上限).

当然,当k = 200时,存在巨大的重叠,可以更直接地取消.这就是我所说的小案例和非小案例:我把它视为一个非小案例,实际上我们可以通过计算"蛮力"这个来逃避((1009^3-199) * ... * 1009^3) / 200!

Answer 3

我不认为你要计算C(N,K),然后减少国防部1009最大的一个,C(1e15,5e14)将需要类似1E16位〜1000兆兆字节

此外,执行snakiles循环回答1e15次似乎可能需要一段时间.您可以使用的是,如果

n = n0 + n1*p + n2*p ^ 2 ... + nd*p ^ d

m = m0 + m1*p + m2*p ^ 2 ... + md*p ^ d

(其中0 <= mi,ni <p)

然后C(N,M)= C(N0,M0)*C(N1,M1)*...*C(ND,ND)模p

请参阅,例如http://www.cecm.sfu.ca/organics/papers/granville/paper/binomial/html/binomial.html

一种方法是使用pascal三角形来构建所有C(m,n)的表,其中0 <= m <= n <= 1009.