AcWing 887. 求组合数 III（Lucas定理）

题面连接

https://www.acwing.com/problem/content/description/889/

思路

我们会发现我们的模数要远小于我们要求得组合数，并且模数p是一个质数，那么我们就可以使用lucas定理来帮我们快速求解次问题，Lucas定理： C a b   m o d   p = C a   m o d   p b   m o d   p × l u c a s ( a / p , b / p )   m o d   p C_a ^b \ mod\ p = C_{a \ mod \ p} ^{{b \ mod \ p}} \times lucas(a/p,b/p) \ mod \ p Cab​ mod p=Ca mod pb mod p​×lucas(a/p,b/p) mod p 在模p的情况下，那么我们很容就能写这个思路的代码，当然我们在处理组合数的计算的时候可以先预处理阶乘或者直接计算，在本题访问次数较少的情况下我们两种做法都可以

关于Lucas定理的证明可以参见： https://www.cnblogs.com/onlyblues/p/15339937.html

代码 预处理阶乘

用时：4047 ms

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e6+10;
ll t,n,m,q,fact[N],invfact[N],mod;
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}


//----------------自定义部分----------------


void init(){
	invfact[0]= fact[0] = 1;//初始化
	for(int i = 1;i >b>>mod;
	init();
	cout= 1;
    }
    return res;
}


int C(int a, int b, int p)
{
    if (b > a) return 0;

    LL resL = 1,resR = 1;
    for (int i = 1, j = a; i > a >> b >> p;
        cout