题三

此题需要注意数的范围超级大！

这题需要用到Lucas定理

Lucas定理

O(plogNlogp)

$$C_a^b \quad mod\quad p= C_{amodp}^{bmodp}*C_{a/p}^{b/p}\quad mod\quad p$$

这就是Lucas定理
证明：
令（将a、b转换为p进制数）：
$$a=a_kp^k+a_{k-1}p^{k-1}+…+a_0p^0\qquad(1)$$
$$b=b_kp^k+b_{k-1}p^{k-1}+…+b_0p^0\qquad(2)$$
又因为二项式展开定理：
$$(1+x)^p=C_p^0+xC_p^1+x^2C_p^2+…+x^pC_p^p\qquad(3)$$
由于p是质数，所以p中是不包含小于p的质因子的，所以当上式对p取模后，右式除第一项和最后一项外将被全部消掉！
那么我们就能得到这样一个等式：
$$(1+x)^p{^k}\quad mod\quad p^k = 1+x^p{^k}$$

对于(1)、(2)和(3)可化下式：

$$(1+x)^a\quad mod\quad p = (1+x)^a((1+x)^{p^1})^{a_1}((1+x)^{p^2})^{a_2}…((1+x)^{p^k})^{a_k}\quad mod\quad p\\=(1+x)^{a_0}(1+x^p)^{a_1}(1+x^{p^2})^{a_2}…(1+x^{p^k})^{a_k}\quad (4)$$

那么我们从$a$个$(1+x)$中选出$b$个&x&来，那我们$x^b$的系数就为$C_a^b$，又因为(2)(4)可知：
$$x^b = x^{b_kp^k+b_{k-1}p^{k-1}+…+b_0p^0}$$
那么：
$$x^{{b_k}p^k}是(1+x^{p^k})^{a_k}中的C_{a_k}^{b_k}*x^{{b_k}{p^k}}$$

$$C_a^b\quad mod\quad p =C_{a_k}^{b_k}C_{a_k-1}^{b_k-1}…C_{a_1}^{b_1}C_{a_0}^{b_0} $$

这里我们写的详细一些：
我们已经将$a、b$转换为了$p$进制，那么$a\quad mod\quad p$的结果就是余数，表现出来就是$a_0$，同理$b\quad mod\quad p = b_0$，再说的简单一点，我们将$a、b$对$p、p^2、p^3、....、p^k$迭代取模，这些数的乘积就是$C_{a_k}^{b_k}C_{a_k-1}^{b_k-1}…C_{a_1}^{b_1}C_{a_0}^{b_0}$，其实就是Lucas定理不断递归下去得到的最终结果。

手写证明：

最终代码，在这里感谢伍老师在lucas定理证明上给予的帮助

#include <iostream>
using LL = long long;
const int N = 30;
int fact[N], infact[N];
int n;

int qmi(int a,int b,int c)
{
    int res = 1;
    while(b)
    {
        if (b & 1) res = (LL)res * a % c;
        a = (LL)a * a % c;
        b >>= 1;
    }
    return res;
}

int C(int a,int b,int c)    //计算组合数
{
    if (b > a) return 0;
    int res = 1;
    for(int i = 1,j = a;i<=b;i++,j--)   //模拟阶乘
    {
        res = (LL)res * j % c;
        res = (LL)res * qmi(i, c - 2, c) % c;   //使用逆元思想和费马小定理来简化计算
    }
    return res;
}

int lucas(LL a,LL b,int c)
{
    if (a < c && b < c) return C(a, b,c);
    return (LL)C(a % c, b % c, c) * lucas(a / c, b / c, c) % c; //递归过程，如之前的证明，我们只需要将每一次的余数用来求C，然后累积即可
}

int main()
{
    std::cin >> n;
    while(n--)
    {
        LL a, b;
        int c;
        std::cin >> a >> b >> c;
        std::cout << lucas(a, b, c) << std::endl;
    }
}