我刚刚看到这个问题，不知道如何解决它。可以请你给我提供的算法，C ++ codeS或想法？

这是一个很简单的问题。鉴于氮，钾的价值，你需要告诉我们二项式系数C（N，K）的值。您可以放心，K＆LT; = N和N的最大值为1,000,000,000,000,000。由于该值可能是非常大的，你需要计算结果取模1009。   输入

输入的第一行包含测试用例T中的数，至多1000的每个下一Ť行包括两个空间分开的整数N和K，其中0℃= K＆其中; = N和1＆所述; = N＆LT; = 1,000,000,000,000,000。   输出

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

输入：   3   3 1   5 2   10 3

输出：   3   10   120

请注意，1009是一个素数。

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

规定：

  p是一个素数。
如果n = A1A2 ... AR的时候写的基地p和
如果k = B1B2 ... BR时候写的基地p

（如果需要垫零）

然后

（正选K）模p =（A1选择B1）*（A2选择B2）* ...... *（AR选择BR）模p。

即n个选择k时用p除以余数是相同的其余部分
该产品（A1选择B1）* ...... *（AR选择BR）时，除以P。
注意：如果BI＆GT;人工智能的AI，然后选择bi为0。
 

因此​​，你的问题归结为找到该产品模数最多登录N /日志1009号形式（的N个位数基地1009号）1009一选择b，其中A＆LT; = 1009和B＆LT; = 1009。

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

请注意：

有关N = 10 ^ 15，N选N / 2以上   2 ^（百万亿），这是这样   超越无符号很长很长。

另外，通过该算法建议   卢卡斯的定理是O（日志N），这是   指数不是试图更快   计算二项式系数   直接（即使你做了一个mod1009   照顾溢出问题的）。

下面是一些$ C $下二项式我写了很长回来了，所有你需要做的是修改它做的操作模1009（有可能是错误的，不一定推荐的编码风格）：

 类二项式
{
上市：
    二项（INT最大值）
    {
        最大=最大+ 1;
        表=新的无符号整型* [MAX]（）;
        的for（int i = 0; I＆LT;最大;我++）
        {
            表[i] =新的无符号整型最大值]（）;

            对于（INT J = 0; J＆LT;最大; J ++）
            {
                表[I] [J] = 0;
            }
        }
    }

    〜二项（）
    {
        的for（int i = 0; I＆LT;最大;我++）
        {
            删除表[I]
        }
        删除表;
    }

    unsigned int类型选择（无符号整数N，无符号整型K）;

私人：
    布尔包含（无符号整数N，无符号整型K）;

    INT最大;
    unsigned int类型**表;
};

unsigned int的二项：请选择（无符号整数N，无符号整型K）
{
    如果（N＆LT; K）返回0;
    如果（K == 0 ||ñ== 1）返回1;
    如果（N == 2＆安培;＆安培; K- == 1）返回2;
    如果（N == 2及和放大器; k == 2）返回1;
    如果（N == k）的回报1;


    如果（包含（N，K））
    {
        返回表[N] [K]
    }
    表[n]的[K] =选择（N-1，k）的+选择第（n-1，K-1）;
    返回表[N] [K]
}

布尔二项式::包含（无符号整数N，无符号整型K）
{
    如果（表[N] [K] == 0）
    {
        返回false;
    }
    返回true;
}
 

I just saw this question and have no idea how to solve it. can you please provide me with algorithms , C++ codes or ideas?

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

Notice that 1009 is a prime.

Now you can use Lucas' Theorem.

Which states:

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.

Thus your problem is reduced to finding the product modulo 1009 of at most log N/log 1009 numbers (number of digits of N in base 1009) of the form a choose b where a <= 1009 and b <= 1009.

This should make it easier even when N is close to 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).

Here is some code for Binomial I had written long back, all you need to do is to modify it to do the operations modulo 1009 (there might be bugs and not necessarily recommended coding style):

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