同余系全家桶

同余系

首先要知道群的概念：

群由两个部分组成 : 元素域 + 运算

而当两个群内的元素经过运算得到的结果也在群内时，这叫封闭性。

举个例子：自然数对加法和乘法是封闭的，实数对除法是封闭的，对开根不是封闭的。

有很多计数题，他们的答案会非常巨大，以前都是用高精度算法输出，一定程度上遏制了技术题技术的发展。受此启发，人们逐渐开始在计数题中使用同余系……

同余系定义：

同余系加法：\(a+b \rightarrow (a+b) \bmod p\)

同余系乘法：\(a \cdot b \rightarrow (a \cdot b) \bmod p\)

为了保持同余系的封闭性，同余系需要包含 \(0\) 到 \(p-1\) 的所有整数。

扩展欧几里得算法（exgcd）

其可以求出方程 \(ax+by=\gcd(a,b)\) 的一组解。

对于 \(ax+by=\gcd(a,b)\)，

令 \(a_2=b,b_2=a \bmod b\)

将 \(a_2,b_2\) 带回原方程可得 \(bx_2+(a \bmod b)y_2=\gcd (a,b)\)

考虑继续化简：

\[bx_2 +(a -\left\lfloor a/b \right\rfloor b)y_2=\gcd(a,b) \]

\[bx_2 +ay2-\left\lfloor a/b \right\rfloor by_2=\gcd(a,b) \]

\[ay_2+b(x_2 -\left\lfloor a/b \right\rfloor y_2)=\gcd(a,b) \]

对比原方程 \(ax+by=\gcd(a,b)\) 可得：\(x=y_2,y=x_2-\left\lfloor a/b \right\rfloor y_2\)

反复迭代直到 \(b=0\)，求出此时的 \(a\) 即可逐层推出原解。

值得注意的是，exgcd 并不基于同余系,所以可能求出来负数,需要模一下变成正数。

逆元

如果一个线性同余方程 \(ax \equiv 1 \pmod b\)，则称 \(x\) 为 \(a \bmod b\) 的逆元，记为 \(a^{-1}\)。

使用方法

对于 \(\frac{a}{b} \bmod p\)，求出 \(b \bmod p\) 的逆元，与 \(a\) 相乘并 \(\bmod p\) 得到结果。

优势：避免了分数的精度问题。

求逆元

exgcd 法

求解 \(ax \equiv 1 \pmod b\)，可以变形为求解 \(ax+by =1\)，使用 exgcd。

code：

点击查看代码

void exgcd(ll a, ll b, ll &x, ll &y) {
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int main() {
	ll x, y;
	cin>>x>>y>>p;
	exgcd(a, p, x, y);
	x=(x % p + p) % p;
	cout<<x;
	return 0;
}

快速幂法

前置知识：费马小定理。

因为 \(ax \equiv 1 \pmod b\)

所以有 \(ax \equiv a^{b-1} \pmod b\)

得 \(x \equiv a^{p-2}\)，用快速幂求解。

code：

见 Lucas 代码。

CRT

先咕着。

Lucas 定理

Lucas 定理是用来求这个东西的：

\[\dbinom{n}{m} \bmod p \]

其中 \(p\) 为较小质数。

其结论为：

\[\dbinom{n}{m} \bmod p = \dbinom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor} \cdot \dbinom{n\bmod p}{m\bmod p} \bmod p \]

因为 \(p\) 值较小，\(\binom{n\bmod p}{m\bmod p}\) 可以直接预处理 \(O(1)\) 求解。而 \(\binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor}\) 可以继续用 Lucas 定理分解递归求解。

证明

首先根据定义可知：

\[\dbinom{p}{n} \bmod p=\dfrac{p!}{n! \cdot (n-p)!} \bmod p \]

可以找到性质：仅当 \(n=0 \vee n=p\) 时，该式结果为 \(1\)，否则为 \(0\)。

据此扩展可得：

\[\begin{align} (a+b)^p &= \sum_{n=0}^p \binom pn a^n b^{p-n}\\&\equiv \sum_{n=0}^p [n=0\vee n=p] a^n b^{p-n}\\ &\equiv (a^p +b^p) \bmod p \end{align} \]

最后将其推广到二项式情况，将 \(p\) 提进来即可。

也可以参考lhx大佬的另类证明

板子传送门

code:

点击查看代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
ll t,n,m,p;
ll jie[100005]={1};
ll ksm(ll y,ll z,ll p){
    y%=p;
	ll ans=1;
    for(int i=z;i;i>>=1,y=y*y%p){
    	if(i&1){
    		ans=ans*y%p;
		}
	}
    return ans;
}
ll C(ll n,ll m){
	if(m>n) return 0;
	return ((jie[n]*ksm(jie[m],p-2,p))%p*ksm(jie[n-m],p-2,p)%p);
}
ll lucas(ll n,ll m){
	if(m==0) return 1;
	return lucas(n/p,m/p)*C(n%p,m%p)%p;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>p;
		jie[0]=1;
		for(int i=1;i<=p;i++){
			jie[i]=jie[i-1]*i%p;
		}	
		cout<<lucas(n+m,n)<<endl;
	}
	return 0;
}

我才不会告诉你这东西其实只有结论需要记略略略

例题： [SHOI2015]超能粒子炮·改

题意：

求

\[\sum_{i=0}^k\dbinom{n}{i} \bmod p \]

且\(p=2333\)

思路：

首先用 Lucas 变形可得：

\[\sum_{i=0}^k \cdot \dbinom{\left\lfloor n/p \right\rfloor}{\left\lfloor i/p \right\rfloor} \cdot \dbinom{n\bmod p}{i\bmod p} \bmod p \]

我草，剩下的不会了。