「相关」CRT&&exLucas

考场上碰到了然后发明(CRT)失败了
还是之前学的时候理解不深刻
虽然现在也没好多少

 

中国剩余定理

用来解决线性同余方程组以及不同模数的合并,满足条件是模数互质
一般运用就是给出类似以下形式的柿子然后解方程组

[ left{ egin{aligned} x equiv a_1mod m_1 \ x equiv a_2mod m_2 \ x equiv a_3mod m_3 \ end{aligned} ight. ]

关于解这个方程组的过程就口胡一下
首先我们设出(n_1,n_2,n_3),然后得到了一下方程组

[ left{ egin{aligned} n_1 equiv a_1mod m_1 \ n_2 equiv a_2mod m_2 \ n_3 equiv a_3mod m_3 \ end{aligned} ight. ]

然后我们发现如果(n_2)是(m_1)的倍数，那么(n_1+n_2)在(mod m_1)的意义下是(a_1)
那么我们发现，如果(n_1+n_2+n_3)是一个可行解
则它们三个满足(n_1)是(m_2)和(m_3)的倍数，(n_2)是(m_1)和(m_3)的倍数，(n_3)是(m_1)和(m_2)的倍数。

那么我们可以构造一种可行解，得到满足上述条件的(n_1,n_2,n_3)并加和，就是我们想要的答案。

int crt(int x,int y){
	int ans=0;
	for(int i=0;i<3;++i){
		int t=mod/Pk[i];exgcd(t,Pk[i],x,y);
		(ans+=1ll*ys[i]*x%mod*t%mod)%=mod;
	}
	return (ans%mod+mod)%mod;
}	

(exLucas)

我们可以用(CRT)来处理模数不是质数时的组合数问题，但是需要保证每个质因子只出现一次。
如果在这个模数中一个质因子出现了多次，那么我们就需要(exLucas)来解决问题。

求一个组合数在模一个非质数下的答案
首先我们分解模数

[P=prod p_{i}^{c_i} ]

我们发现每个部分都是互质的，(CRT)合并即可

然后我们考虑计算单个组合数，即

[C_{n}^{m} mod p^c ]

组合数中可能含有(p)，所以我们把组合数展开并把(p)提出来，即

[frac{frac{n!}{p^{c_1}}}{frac{m!}{p^{c_2}} imesfrac{(n-m)!}{p^{c_3}}} imes p^{c_1-c_2-c_3} ]

接下来是第三步，算如下柿子

[frac{n!}{p^c} mod p^k ]

偷一个例子来
(n=22,p=3,p^k=9),将柿子展开后我们得到
(22!=3^{7} imes7! imes(1 imes2 imes4 imes5 imes7 imes8) imes(10 imes11 imes13 imes14 imes16 imes17) imes(19 imes20 imes22))
因为(3)的倍数有(7)个，所以有(7!)。
发现第二个括号中的数和第一个括号在模(9)的意义下是一样的，所以我们合起来。
发现最后一个括号是(22\%9)的剩余部分。
最终柿子变成了(22!=3^{7} imes7! imes(1 imes2 imes4 imes5 imes7 imes8)^{2} imes(19 imes20 imes22))
第一部分快速幂，第二部分递归，第三部分和第四部分暴力枚举或预处理。

int Fac(int n,int p,int pk){
	if(!n) return 1;int ans=1;
	for(int i=1;i<pk;++i) if(i%p) ans=1ll*ans*i%pk;
	ans=qpow(ans,n/pk,pk);
	for(int i=1;i<=n%pk;++i) if(i%p) ans=1ll*ans*i%pk;
	return 1ll*ans*Fac(n/p,p,pk)%pk; 
}

然后我们回到组合数的处理上

int C(int x,int y,int p,int pk){
	if(x<y) return 0;
	int f1=Fac(x,p,pk),f2=Fac(y,p,pk),f3=Fac(x-y,p,pk),cnt=0;
	for(int i=x;i;i/=p) cnt+=i/p;
	for(int i=y;i;i/=p) cnt-=i/p;
	for(int i=x-y;i;i/=p) cnt-=i/p;
	return 1ll*f1*Inv(f2,pk)%pk*Inv(f3,pk)%pk*qpow(p,cnt,pk)%pk;
}

注意(Inv)可以用(exgcd)或者(qpow)求。
最后再用(CRT)合并即可。