同余定理
同余性质
同余性质是指在任意情况下，都有：
- $n\times m\bmod p$=$(n\bmod p)\times(m\bmod p)\bmod p$
- $n+m\bmod p$=$(n\bmod p)+(m\bmod p)\bmod p$
- $n-m\bmod p$=$(n\bmod p)-(m\bmod p)\bmod p$
除法不满足同余性质。
欧拉定理
欧拉函数：$\varphi(n)$ 表示在 $1$ 和 $n$ 之间与 $n$ 互质的个数，即 $\sum_{i=1}^{n}[\gcd(i,n)=1]$。
欧拉定理：如果 $\gcd(n,p)=1$，则有 $n^p\equiv1\pmod p$。
乘法逆元
乘法逆元指如果 $a\times b\equiv1\pmod p$，则称 $b$ 为 $a$ 的 $p$ 意义下逆元。
快速幂求逆元
因为 $a\times b\equiv1\pmod p$，则有 $a\times b\equiv a^{p-1}\pmod p$，同时除以 $a$，则有 $b\equiv a^{p-2}\pmod p$，所以可以用快速幂求逆元。
递推求逆元
令 $div=\lfloor\frac{i}{p}\rfloor$，$mod=i\mod p$，则有：
$$div\times i+mod\equiv 0\pmod p$$
同时转为逆元，则：
$$div^{-1}\times i{-1}+mod\equiv 0\pmod p$$
$$i^{-1}\equiv div^{-1}\times mod^{-1}\pmod p$$
$$i^{-1}\equiv div=\lfloor\frac{i}{p}\rfloor^{-1}\times(i\bmod p)^{-1}\pmod p$$
就可以递推求了。
ll inv[MAXN];
inline void prework(ll mod){
inv[1]=1;//初始值
for(int i=2;i<MAXN;++i){
inv[i]=(mod-mod/i)*inv[mod%i]%mod;//递推式
}
}
gcd 定理
exgcd
$$a\times x_1+b\times y_1=\gcd(a,b)$$
$$b\times x_2+(a\bmod b)\times y_2=\gcd(a,a\bmod b)$$
之后不断往下递归就可以了。
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;
y=0;//肯定有这么一组
return a;
}
ll d=exgcd(b,a%b,x,y);//公式
x=y;
y=d-(a/b)*y;//公式
return d;
}
裴蜀定理
裴蜀定理指如果要满足 $ax+by=c$，则需要满足 $\gcd(a,b)\mid c$。没什么特别好讲的，主要主语结论。
积性函数
欧拉函数
欧拉函数上面讲到过，其实可以拆解成：$\Pi_{p\in Prime,p\mid n}(p-1)$，所以，可以用欧拉筛筛出来。
莫比乌斯函数
莫比乌斯函数的定义是这样的：
$$\mu(n)=\begin{cases}
1&n\in Prime\
0&p^2\mid n,p\in Prime\
(-1)k&n=\Pi_{i=1}p_i^{c_i},p_i\in Prime
\end{cases}$$
这也是积性函数，所以可以用欧拉筛筛出来。
莫比乌斯反演
有一个性质，$\sum_{d\mid n}\mu(d)=[n=1]$，所以，这可以将形如：
$$F(n)=\sum_{d\mid n}f(\lfloor\frac{n}{d}\rfloor)$$
$$f(n)=\sum_{d\mid n}\mu(d)\times F(\lfloor\frac{n}{d}\rfloor)$$
还可以将形如：
$$[\gcd(a_1,a_2,a_3\dots a_n)=1]$$
变成：
$$\sum_{d\mid a_1,d\mid a_2,d\mid a_3\dots d\mid a_n}\mu(d)$$
例题
基于上面的反演公式，可以转化为：
$$\sum_{d=1}{n}\sum_{t=1}\rfloor}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{d\times t}\rfloor}\varphi(i)\sum_{j=1}^{\lfloor\frac{m}{d\times t}\rfloor}\varphi(j)$$
之后掏出一个 $G(n)=\sum_{i=1}^{n}\varphi(i)$，有：
$$\sum_{d=1}{n}\sum_{t=1}\rfloor}\mu(t)\times G(\lfloor\frac{n}{d\times t}\rfloor)\times G(\lfloor\frac{m}{d\times t}\rfloor)$$
再掏出一个 $H(n,m,t)=\sum_{i=1}^{t}\mu(t)\times G(\lfloor\frac{n}{i}\rfloor)\times G(\lfloor\frac{m}{i}\rfloor)$。
$$\sum_{d=1}^{n}H(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor,\lfloor\frac{t}{d}\rfloor)$$
之后预处理加上数论分块优化就可以了。
#include<bits/stdc++.h>
#define MAXN 50005
#define MAXM 55
#define MOD 23333
using namespace std;
int t,n,m;
int phi[MAXN],mob[MAXN];
vector<int> prim,G[MAXN],S[MAXM][MAXM];
bool flag[MAXN];
inline void prework(){
flag[1]=phi[1]=mob[1]=1;
for(int i=2;i<MAXN;++i){
if(!flag[i]){
prim.push_back(i);
phi[i]=i-1;
mob[i]=-1;
}
for(int j=0;j<prim.size()&&i*prim[j]<MAXN;++j){
flag[i*prim[j]]=true;
if(i%prim[j]){
phi[i*prim[j]]=phi[i]*(prim[j]-1)%MOD;
mob[i*prim[j]]=-mob[i];
}else{
phi[i*prim[j]]=phi[i]*prim[j]%MOD;
break;
}
}
}
for(int i=1;i<MAXN;++i){
G[i].push_back(0);
for(int j=1;i*j<MAXN;++j){
G[i].push_back((G[i].back()+phi[i*j])%MOD);
}
}
for(int i=1;i<MAXM;++i){
for(int j=1;j<MAXM;++j){
S[i][j].resize(MAXN/max(i,j)+1);
for(int d=1;d*max(i,j)<MAXN;++d){
for(int k=1;k*d*max(i,j)<MAXN;++k){
(S[i][j][k*d]+=G[d][i]*G[d][j]%MOD*mob[d]%MOD)%=MOD;
}
}
for(int k=1;k*max(i,j)<MAXN;++k){
(S[i][j][k]+=S[i][j][k-1])%=MOD;
}
}
}
}
inline int blocked(){
int ans=0,lim=m/MAXM;
for(int i=1;i<=lim;++i){
for(int j=1;i*j<=lim;++j){
(ans+=1ll*mob[i]*G[i][n/i/j]%MOD*G[i][m/i/j]%MOD)%=MOD;
}
}
for(int l=lim+1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
(ans+=((S[n/l][m/l][r]-S[n/l][m/l][l-1])%MOD+MOD)%MOD)%=MOD;
}
return ans;
}
int main(){
prework();
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
if(n>m){
swap(n,m);
}
printf("%d\n",blocked());
}
return 0;
}
组合计数
卡特兰数
卡特兰数是指从 $n$ 个元素中选 $m$ 个数的方案，具体可以用证明法。
- 设 $A_{n}^{m}$ 为从 $n$ 个里面选取 $m$ 个数，包含顺序不同的情况，为 $\frac{!n}{!(n-m)}$
- 那么不包含顺序的 $C_{n}^{m}$ 为 $\frac{A_nm}{A_m1}$，是 $\frac{!n}{!(n-m)\times !m}$。
- 下面两项再取模的时候可以乘以逆元。
容斥原理
容斥是指去除重复的情况。例如要求 $|S1\cap S2|$，则可以用 $|S1|+|S2|-|S1\cup S2|$。这个就是容斥原理。
例题
这一道题目考虑正难则反。首先令 $ans=\sum c_i\times d_i$，减去不合法的情况。
首先，我们把它当成一个完全背包，处理出来一个 dp 数组存储方案数，转移方程为 $dp_i\to dp_i+dp_{i-v_i}$。
考虑减去不合法的情况为更多的硬币，所以就是 $ans\to ans-dp_{V-d_i-1}\times c_i$。
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
typedef long long ll;
ll dp[MAXN];
int main(){
int c[5],test;
scanf("%lld %lld %lld %lld %lld",&c[1],&c[2],&c[3],&c[4],&test);
dp[0]=1;
for(int i=1;i<=4;++i){
for(int j=c[i];j<MAXN;++j){
dp[j]+=dp[j-c[i]];
}
}
while(test--){
int d[5],sum,ans=0;
scanf("%lld %lld %lld %lld %lld",&d[1],&d[2],&d[3],&d[4],&sum);
for(int i=0;i<=15;++i){
int cnt=sum,val=1;
for(int j=1;j<=4;++j){
if((i>>(j-1))&1){
cnt-=c[j]*(d[j]+1);
val*=-1;
}
}
if(cnt<0){
continue;
}
ans+=val*dp[cnt];
}
printf("%lld\n",ans);
}
return 0;
}