数学基础模板

数学基础

此部分由我前队友完成。浏览体验可能会有所不同因为水平比我强


有些地方无法正常浏览，可能是因为我队友有些用的LateX语法，markdown渲染不出来

组合数

1. 求组合数

根据不同的数据范围，求组合数也可以运用不同的方法。总的式子：

$C_a^b=\frac{a!}{b!(a-b)!}$

表示从$a$个物品中选出$b$个的方案数。

(1) 递推法

使用递推式$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$

证明：考虑已经得知了$C_{a-1}^k,k\in[0,b]$的结果，那么当前有$a$个物品时，第$a$个物品要么被选，要么不被选中。若被选中，则方案一共有$C_{a-1}^{b-1}$个，若不被选中，则方案有$C_{a-1}^b$个，方案累加，得证。

时间复杂度$O(n^2)$

void init(){
    for (int i=0;i<N;++i){
        for (int j=0;j<=i;++j){
            if (!j) C[i][j] = 1;
            else{
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % M;
            }
        }
    }
}

(2) 通过预处理逆元的方式求组合数

直接求出$a!,\frac{1}{b!},\frac{1}{(a-b)!}$，然后再相乘。

时间复杂度$O(n\log n)$

int n;
const int N = 1e5 + 5;
const ll M = 1e9 + 7;
ll fac[N], invf[N];// 阶乘 阶乘的逆元

void init(){
    fac[0] = invf[0] = 1LL;
    for (int i=1;i<N;++i){
        fac[i] = fac[i-1] * i % M;
        invf[i] = invf[i-1] * qmi(i, M-2, M) % M;
    }
}

int main(void){
    scanf("%d", &n);
    init();
    ll a, b;
    for (int i=1;i<=n;++i){
        scanf("%lld%lld", &a, &b);
        ll ans = fac[a] * invf[b] % M * invf[a - b] % M;
        printf("%lld\n", ans);
    }
    
    return 0;
}

(3) 分解质因数法求组合数（高精度）

首先，可以把$a!$写成$a!=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}$的形式，那么$C_a^b$的答案肯定可以写成$C_a^b=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k},\forall i\in[1,k],b_i\leq a_i$。

因此，设$s_i$为 $a!$ 中包含的质因子 $p_i$ 的个数减去$b!,(a-b)!$中包含的$p_i$ 的个数，则$C_a^b=\prod_{i=1}^{k} p_i^{s_i}$。

那么，$a!$包含的质因子个数为多少呢？答案是$\lfloor\frac{a}{p}\rfloor+\lfloor\frac{a}{p^2}\rfloor+\lfloor\frac{a}{p^3}\rfloor...$。

• 代码：

const int N = 5000 + 5;
int p[N], sa[N], cnt;
bool st[N];

void Euler(int n){
	for (int i=2;i<=n;++i){
		if (!st[i]) p[++cnt] = i;
		for (int j=1;p[j]<=n/i;++j){
			st[p[j] * i] = true;
			if (i % p[j] == 0) break;
		}
	}
}

int get(int n, int p){
	int res = 0;
	while (n){
		res += n/p;
		n/=p;
	}
	return res;
}

vector<int> mul(vector<int>& A, int b){
    vector<int> res; int t = 0;
    for (int i=0;i<A.size();++i){
        t += A[i]*b;
        res.push_back(t % 10), t /= 10;
    }
    while (t){ res.push_back(t%10), t /= 10;}
    while (res.back()==0 && res.size()>1) res.pop_back();
    return res;
}

int main(void){
	int a, b;
	scanf("%d%d", &a, &b);
	Euler(a);
	for (int i=1;i<=cnt;++i){
		int cur = p[i];
		sa[i] = get(a, cur) - get(a-b, cur) - get(b, cur);
	}
	
	vector<int> res;
	res.push_back(1);
	for (int i=1;i<=cnt;++i){
		for (int j=0;j<sa[i];++j){
			res = mul(res, p[i]);
		}
	}

	for (int i=res.size()-1;i>=0;--i){
		printf("%d", res[i]);
	}
	puts("");
	
	return 0;
}

(4) Lucas定理求组合数

• Lucas定理：$C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p)$

• 代码

其中，组合数直接通过公式$C_a^b=\frac{a!}{b!(a-b)!}=\frac{a\times (a-1)\times...\times (a-b+1)}{b!}$求得

ll C(ll a, ll b, ll p){
	if (b > a) return 0;
	ll res = 1;
	for (int i=1, j=a;i<=b;++i, --j){
		res = res * j % p; // 分子
		res = res * qmi(i, p-2, p) % p; // 分母
	}
	return res;
}

ll lucas(ll a, ll b, ll p){
	if (a<p && b<p) return C(a, b, p);
	return C(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
}

(5) 取对数求组合数（可能有浮点误差）

此种方法大概可以计算1000以内的组合数。

先假设$m\leq \frac{n}{2}$吧，否则因为$C(n,m)=C(n,m-n)$，令 $m=m-n$。

则$x=\ln C(n,m)=\ln (\frac{n!}{m!(n-m)!})=\sum\limits _{i=1}^n\ln i-\sum\limits _{i=1}^m\ln i-\sum\limits _{i=1}^{n-m}\ln i$

这样就可以直接计算前缀和$\ln n$，则$C(n,m)=e^x$。

2. 常用公式

(1) 二项式定理

(x+y)^n=\left(\begin{array}{} n\\ 0 \end{array}\right)x^ny^0+\left(\begin{array}{} n\\ 1 \end{array}\right)x^{n-1}y^1+...+\left(\begin{array}{} n\\ n-1 \end{array}\right)x^1y^{n-1}+\left(\begin{array}{} n\\ n \end{array}\right)x^0y^n

也可写成(x+y)^n=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\right)x^{n-k}y^k=\sum\limits_{k=0}^n\left(\begin{array}{} n\\ k \end{array}\right)x^{k}y^{n-k}

其中，\left(\begin{array}{} n\\ k \end{array}\right)=C_n^k=\frac{n!}{k!(n-k)!}。

二项式定理的一个常用形式为$(1+x)^n=\sum\limits_{k=0}^n C_n^kx^k$。

那么很明显，$(1-x)^n=\sum\limits_{k=0}^n (-1)^kC_n^kx^k$

(2) 其他的一些小公式

$C_n^0+C_n^1+...+C_n^n=2^n$（从$n$取任意个数，显然二进制取或不取）

$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$（类似DP思想，对于第$b$个数，取或不取）

$C_{m+n}^n=C_m^0C_n^n+C_m^1C_n^{n-1}+...+C_m^nC_n^0$（从$m$个数取$n$个，$n$个取0个开始遍历）

$C_n^m=C_n^{n-m}$（显然从$n$中取$m$个的方案数和从$n$中取$n-m$个的方案数是一样的）

（这些递推式还是挺容易证明的就不写了，敲公式好累）

(2) 乘法原理和加法原理：类类独立，步步相关

1. 加法原理：做一件事情，完成它可以有$n$类办法，在第一类办法中有$m_1$种不同的方法，在第二类办法中有$m_2$种不同的方法，……，在第$n$类办法中有$m_n$种不同的方法。那么完成这件事共有$N=\sum_{i=1}^n m_i$种不同的方法。

2. 乘法原理：做一件事情，完成它需要分成n个步骤，做第一步有$m_1$种不同的方法，做第二步有m2种不同的方法，……，做第$n$步有种$m_n$不同的方法，那么完成这件事有$N＝\prod_{i=1}^n m_i$种不同的方法。

(3) 可重复元素的组合问题

从n个元素中，可重复的挑选m个元素组成集合，求：不同的集合有多少个？

答案：$C_{n+m-1}^m$

证明：隔板法。

∣∗∣∗∗∗∗∣∣∗∗∗∣∣∗∣（|是边界，*是球）

假设这里有n个盒子，m个球，如果有k个球被放在了第i个盒子里，那么就相当于第i个数被选了k次。那么去掉两端边界，就相当于摆放n-1个盒子的边界和m个球有多少种摆放方式。从里面选择r个位置放球 剩余的都是盒子边界，因此答案就是$C_{n+m-1}^m$。

这里有位老哥用dp在$O(n^2)$搞定了，俺觉得也可以一看wwww，部分dp表真是一个好东西啊。

https://blog.csdn.net/m0_37602827/article/details/100624871

3. 常用定理

(1) Lucas定理

结论：$C_a^b \equiv C_{a\mod p}^{b \mod p}\times C_{a/p}^{b/p} (\mod p)$ （$p$为素数）

它还可以写成如下形式：

若$p$为素数，则$n$的$p$进制表示为$(a_k,a_{k-1},...,a_0)$，$m$的$p$进制表示为$(b_k,b_{k-1},...,b_0)$

则$C_n^m\equiv C_{a_k}^{b_k}·C_{a_{k-1}}^{b_{k-1}}...C_{a_0}^{b_0} (\mod p)$

很容易看出来，它就是形式一运用数学归纳法可以得出的结论。

证明：

引理1 $C(p,x) \equiv 0(\mod p), 0<x<p$

证明：$C(p,x)\equiv \frac{p!}{x!(p-x)!}\equiv \frac{p\times (p-1)!}{x\times(x-1)\times(p-x)!} $

由于$p$为素数，所以$\forall x\in(0,p),(p,x)=1$，故$x|C_{p-1}^{x-1}$，则$p|(\frac{p}{x}C_{p-1}^{x-1})$。

所以$C(p,x) \equiv p\times(x^{-1} \mod p)\times C(p-1,x-1)\equiv 0\mod p$

引理2 $(1+x)^p \equiv (1+x^p) \mod p$

根据二项式定理可得$(1+x)^p=\sum\limits _{k=0}^pC_p^kx^k$

由引理1可得$\sum\limits _{k=0}^pC_p^kx^k\equiv C(p,0)x^0+C(p,p)x^p\equiv (1+x^p) \mod p$

下面正式推导Lucas定理。

假设$n=q_1p+r_1,m=q_2p+r_2$，则$q_1=n/p,q_2=m/p$

$(1+x)^n\equiv (1+x)^{q_1p+r_1}\equiv (1+x)^{q_1p}\times(1+x)^{r_1}\equiv [(1+x)^p]^{q_1}\times(1+x)^{r_1} \\ (1+x^p)^{q_1}\times(1+x)^{r_1} \equiv \sum\limits _{i=0}^{q_1}C(q_1,i)x^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,j)x^{j} (\mod p)$

又$(1+x)^n=\sum\limits _{i=0}^{n}C(n,i)x^{i}$

$\therefore \sum\limits _{i=0}^{n}C(n,i)x^{i}\equiv \sum\limits _{i=0}^{q_1}C(q_1,i)x^{p\times i}\times \sum\limits _{j=0}^{r_1}C(r_1,j)x^{j} (\mod p)$

由二项式定理可知，$C_n^m$为$(1+x)^n$展开式中$x^m$项前面的系数

$\because m=q_2p+r_2,\therefore q_2=m/p,r_2=m-\lfloor \frac{m}{p} \rfloor \times p$

$C(n,m)x^{m}\equiv C(q_1,q_2)x^{p\times q_2}\times C(r_1,r_2)x^{r_2} (\mod p)$

即$C_n^m\equiv C_{q_1}^{q_2}·C_{r_1}^{r_2} (\mod p)$，得证。

推论1 $C(n,m)$为奇数的充要条件为，在二进制表示下（$p=2$），$\forall i\in[0,k],a_i\geq b_k$。

证明：首先，$C(0,0)=1,C(0,1)=0,C(1,0)=1,C(1,1)=1$。

考虑$C(n,m)\mod 2$，则对于$n$上的为1的位$a_i$，$b_i$能取0或1，对于$a_i=0$，则$b_i$必须为0，得证。

例题：HDU4349 Xiao Ming’s Hope 结论就是$2^{sum(a_i=1)}$ 这玩意还真会考到啊orz

(2) 扩展Lucas定理

前置知识：卢卡斯定理 中国剩余定理

扩展Lucas定理用于求解以下公式：

$C_a^b \mod p$，其中$p$不一定是质数。

由整数的唯一分解定理，对$p$进行质因数分解，$p=p_1^{a_1}\times p_2^{a_2}\times .. \times p_k^{a_k}$，显然$\forall i,j \in [1,k], i\neq j, (p_i^{a_i},p_j^{a_j})=1$。

提高篇中已证明

筛法

1. 埃氏筛

• 主要思想：筛掉所有质数的倍数
• 代码

// 为什么j可以从i*i开始?
// 假设i=7, 那么比i小的所有的质数, 已经把2*7,3*7,5*7这样的数筛掉了, 所有可以直接从7*7开始筛
void Eratosthenes(){
    for (int i=2;i<=n;++i) st[i] = 1;
    for (int i=2;i<=n;++i){
        if (st[i]){
            p[++cnt] = i;
            if ((ll)i*i > n) continue;
            for (int j=i*i;j<=n;j+=i){
                st[j] = false;
            }
        }
    }
}

• 时间复杂度分析

  如果是筛所有的数的倍数，那么会筛$\frac{N}{2}+\frac{N}{3}+...+\frac{N}{N}=N\times(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N})$ 次。

​ 由于调和级数$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N}=ln(N+1)+r$，$r$为欧拉常数，$r\approx 0.5772156649$。因此，时间复杂度可近似为$O(NlnN)<O(NlogN)$。

​ 当只筛质数时，由质数分布定理可得$N$中约有$\pi(N)=\frac{N}{ln N}$个质数，因此时间复杂度估算结果为$O(\frac{NlnN}{lnN})$，即非常接近$O(N)$。在实际计算下，埃氏筛的时间复杂度为$O(NloglogN)$。

2. 欧拉筛

• 主要思想：每个合数只被筛一次的算法。
• 代码

void Euler(){
    for (int i=2;i<=n;++i){
        if (!st[i]) p[++cnt] = i;
        for (int j=1;p[j]<=n/i;++j){
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}
// 为什么每个合数只会被筛一次呢?
// 因为每个合数只会被它的最小质因子筛掉
// 从小到大枚举p[j],当i%p[j]==0时, break。
// 1. 当i%p[j]==0时。说明p[j]是i的最小质因子, 那么p[j]一定也是p[j]*i的最小质因子
// 2. 当i%p[j]!=0时, 说明p[j]比i的最小质因子还小, 那么p[j]一定是p[j]*i的最小质因子

• 时间复杂度：$O(N)$。

质数

• 定义：大于1，且除了1和它本身之外不再有其他因数的自然数。
• 质数分布定理：$1$~$n$间的质数大概有$\pi(n)=\frac{n}{\ln n}$个

互质数：两个或多个整数的公因数只有1的非0自然数。

• 小性质：最小的9个质数相乘，答案在int范围内。

约数

1. 试除法求约数

(1) 求所有的质因数

void div(int x){
	for (int i=2;(ll)i*i<=x;++i){
		int cnt = 0;
		while (x%i==0){
			x /= i; cnt++;
		}
		if (cnt) printf("%d %d\n", i, cnt);
	}
	if (x > 1) printf("%d %d", x, 1);
	puts("");
}

(2) 求所有的约数

使用筛法先筛质数，再通过dfs枚举约数

int n, cnt, tot, dn;
const int N = 5e4 + 5;
bool st[N];
int p[N], d[N];
pii f[N];

void dfs(int u, int x){
	if (u > tot){
		d[++dn] = x; return ;
	}
	for (int i=0;i<=f[u].yy;++i){
		dfs(u + 1, x);
		x *= f[u].xx;
	}
}

void solve(){
	int a0, a1, b0, b1;
	scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
	int n = b1;
	tot = 0;
	for (int i=1;p[i]<=n/p[i];++i){
		if (n % p[i] != 0) continue;
		int sm = 0;
		while (n % p[i] == 0) n /= p[i], ++sm;
		f[++tot] = pii(p[i], sm);
	}
	if (n > 1) f[++tot] = pii(n, 1);
	dn = 0;
	dfs(1, 1);
}

2. 约数个数

任何一个正整数$n$都可以表达为如下形式：

$n=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}$，其中，$\forall i\in [1,k], p_i$为质数

那么，对于$n$的任意约数$\alpha$，都可以将$\alpha$写成如下形式：

$\alpha=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k}$，其中，$\forall i\in [1,k]$，$0\leq b_i \leq a_k$

那么对于每一个$b_i$，都有$(a_i+1)$种取法，因此，$n$的所有约数之和为$(a_1+1)(a_2+1)...(a_k+1)$

• 小性质：所有int范围内的数，约数之和最多的约为1500

小例子:求n!的约数之和

int n, cnt;
const int N = 1e6 + 5;
int p[N], num[N];
bool st[N];

void Euler(int n){
    for (int i=2;i<=n;++i){
        if (!st[i]) p[++cnt] = i;
        for (int j=1;p[j]<=n/i;++j){
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
}

int main(void){
    scanf("%d", &n);
    Euler(N - 1);
    for (int i=2;i<=n;++i){
        if (st[i]) continue;
        for (ll j = i;j<=n;j*=i){
            num[i] += n / j;
        }
    }
    for (int i=2;i<=n;++i){
        if (num[i]){
            printf("%d %d\n", i, num[i]);
        }
    }

    return 0;
}

3. 约数之和

$\sum \alpha_i=(p_1^0+ p_1^1+ ...+ p_1^{a_1})(p_2^0+ p_2^1+ ...+ p_2^{a_2})...(p_k^0+ p_k^1+ ...+ p_k^{a_k})$

展开该式子，就可以得到$\alpha=p_1^{b_1}\times p_2^{b_2}\times ...\times p_k^{b_k}$，所有的$b_i$取值的组合相加。实际上，这个式子展开一共有$(a_1+1)(a_2+1)..(a_k+1)$项，也对应了约数个数。

4. 欧几里得算法

欧几里得算法基于的性质：

1. 若$d|a, a|b$，则$d|(ax+by)$

2. $(a,b)=(b,a~mod~b)$

第二条性质证明：

$\because a~mod~b=a-\lfloor \frac{a}{b} \rfloor\times b$，令$c=\lfloor \frac{a}{b} \rfloor$

则问题等价于证明$(a,b)=(b,a-c\times b)$

这个证明方法就和裴蜀定理的证明差不多。

证明：令$d=gcd(a,b)$，则$d|a,d|b$，易得$d|(a-c\times b)$。则$d$为$b,(a-c\times b)$的公因数。

那么令$D=(b,a-c\times b)$，$d\leq D$。

$D|b,D|(a-c\times b)$，易得$D|a$，则$D\leq (a,b)=d$。

因此$d=D$，即$d=gcd(b,a-c\times b)$

欧几里得算法模板

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

欧拉函数

1. 欧拉函数的定义

• 定义$\varphi(N)$为$1$~$N$中与$N$互质的数，假设$N$可以表达为$p_1^{a_1}\times p_2^{a_2}...p_k^{a_k}$，$\forall i\in [1,k], p_i$为质数，$a_i>0$

  则$\varphi(N)=N\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$

特别的，规定$\varphi(1)=1$。（唯一和1互质的数就是1本身）

证明：容斥原理

1. 先去掉1~N中$p_1$的倍数，再去掉1~N中$p_2$的倍数，……直到去掉1~N中$p_k$的倍数。那么，此时答案就是

   $N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}$

2. 这个答案，将$p_i\times p_j, (i,j\in[1,k], i\neq j)$重复减去了多次，需要把它们加回来

   $N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+...+\frac{N}{p_{k-1}p_k}$

3. 考虑这样的三元组$p_ap_bp_c$，它们先是被1中的式子$p_a,p_b,p_c$减去了三次，又在2中的式子$p_ap_b,p_ap_c,p_bp_c$中加了三次，总体没加也没减。因此要把三元组的倍数从$N$中减去

   $N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+...+\frac{N}{p_{k-1}p_k}-\frac{N}{p_1p_2p_3}-...-\frac{N}{p_{k-2}p_{k-1}p_{k}}$

4. 以此类推，最终化简上面的式子，可得

   $N\times(1-\frac{1}{p_1}-...-\frac{1}{p_k}+\frac{1}{p_1p_2}+...+\frac{1}{p_{k-1}p_k}-...)\\=N\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$

• 时间复杂度：欧拉函数时间复杂度最大的地方在于分解质因数，因此时间复杂度为$O(\sqrt N)$。

欧拉函数模板

int phi(int x){
    int res = x;
    for (int i=2;(ll)i*i<=x;++i){
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

2. 欧拉函数的性质

性质1

• $\sum a=\frac{n\times \varphi(n)}{2}, n>1, a\in[1,n),(a,n)=1$。

性质2

• $\forall n>2,\varphi(n)$为偶数。

证明：$\because (n,x)=(n,n-x), n>x$

假设$\exist x\in[1,n)$，$(n,x)=(n,n-x)=1,x=n-x, n>2$，则$n=2x$，矛盾。

$\therefore[1,n)$中与$n$互质的数均是成对出现的，因此$[1,n)$与$n$互质的数是偶数，即$\varphi(n)$为偶数。

观察$(n,x)=(n,n-x)=1$，也说明了任意一对与$n$互质的数，相加均为$n$，所以有$\sum a = \frac{n\times\varphi(n)}{2}$

性质3

• $\sum\limits _{d|n} \varphi(d)=n$

设$f(n)=\varphi * I=\sum\limits _{d|n}\varphi(d)$，则$f(n)$为一个积性函数。

将$n$唯一分解为$n= \prod_{i=1}^kp_i^{a_i} = p_1^{a_1}p_2^{a_2}..p_k^{a_k}$，则

$f(p_i^{a_i})=\varphi(1)+\varphi(p_i)+..+\varphi(p_i^{a_k})\\=1+(p-1)+..+(p^k-p^{k-1})=p^k$

$f(n)=f(p_1^{a_1})\times f(p_2^{a_2})\times ..\times f(p_k^{a_k})=\prod_{i=1}^kp_i^{a_i}=n$，证毕。

性质4

• 欧拉函数为积性函数，但不是完全积性函数，当$(n,m)=1$时，满足$\varphi(m\times n)=\varphi(m)\times \varphi(n)$。那么显然，当$n$唯一分解后，$\varphi(n)=\prod_{i=1}^k\varphi(p_i^{a_i})$。

证明：若$(n,m)=1$，则$n,m$没有相同的质因子，记$n$的质因子个数为$c_1$，$m$的质因子个数为$c_2$，则

$\varphi(n)\times \varphi(m)=n\times m\times \prod_{i=1}^{c_1}(1-\frac 1 {p_i})\times \prod_{i=1}^{c_2}(1-\frac 1 {p_i})=\prod_{i=1}^{c_1+c2}(1-\frac 1 {p_i})=\varphi(n\times m)$

例题：cf776E The Holmes Children

性质5

• $\frac {\varphi(n)} n=\sum\limits_{d\mid n}\frac{\mu(d)}{d}$。

写成狄利克雷卷积的形式

$\varphi * I=id$，$\varphi * I * \mu=id * \mu$

$\varphi * (I * \mu)=id * \mu$

$\varphi*e=id*\mu$

即$\varphi(n)=\sum\limits _{d|n}\frac n d\times \mu(d)$，也就是$\frac {\varphi(n)} n=\sum\limits_{d\mid n}\frac{\mu(d)}{d}$

性质6

当$n=p^k$时，$\varphi(n)=p^k-p^{k-1}$

证明：当$n$只有一个质因数时，$\varphi(n)=p^k\times(1-\frac 1 p)=p^k-p^{k-1}$

3. 筛法求欧拉函数

假设目前已知$\varphi(i)$的值，$p_j$为某一质数，求$\varphi(i\times p_j)$的值。

将$i$表示为$p_1^{a_1}\times p_2^{a_2}...p_k^{a_k}$，$\varphi(i)=i\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$，

1. $i\%p_j==0$时，$i\times p_j$中不存在新的质因子

   $\therefore \varphi(i\times p_j)=i\times p_j\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})=\varphi(i)\times p_j$

2. $i\%p_j\neq 0$时，$p_j$为新的质因子

   \begin{align} & \therefore \varphi(i\times p_j)=i\times p_j\times (1-\frac{1}{p_1})\times(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\times (1-\frac{1}{p_j})\\ & =\varphi(i)\times p_j\times(1-\frac{1}{p_j})\\ & =\varphi(i)\times(p_j-1) \end{align}

• 代码

int n, cnt;
const int N = 1e6 + 10;
int E[N], p[N];
bool st[N];

void Eulers(){
    E[1] = 1;
    for (int i=2;i<=n;++i){
        if (!st[i]){
            p[++cnt] = i;
            E[i] = i - 1;
        }
        for (int j=1;p[j]<=n/i;++j){
            int t = p[j] * i;
            st[t] = true;
            if (i % p[j] == 0){
                E[t] = E[i] * p[j];
                break;
            }
            E[t] = E[i] * (p[j] - 1);
        }
    }
}

快速幂

1. 定义

// 求a^b % p 时间复杂度O(logN)
ll qmi(ll a, ll b, ll p){
    ll res = 1LL % p;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

2. 快速幂求逆元

乘法逆元的定义

​ 若对于整数$b,m$，有$(b,m)=1$（即$b,m$互质），并且对于任意的整数$a$，如果满足$b|a$，则$\exist x\in N$，$s.t.~~\frac{a}{b}=a\times x(mod~ m)$，则称$x$为$b$的模$m$乘法逆元，记为$b^{-1}(mod~m)$。

• $b$存在乘法逆元的充要条件是$(b,m)=1$，当$m$为质数时，$b$的乘法逆元为$b^{m-2}$。

• 小性质

  $\frac{a}{b} \equiv a\times x(mod ~m)$ $\frac{a}{b} \equiv a\times b^{-1}(mod ~m)$

  则$a\equiv a\times b \times b^{-1}(mod ~m)$ 即 $b\times b^{-1} \equiv 1(mod ~m)$

• 费马小定理

  $\forall p$为质数，$a$为任意整数，有$ a^{p-1}\equiv 1(mod ~p)$

  小推论：$b\times b^{p-2}\equiv 1(mod~p)$，因此$b$的乘法逆元为$b^{p-2}$

扩展欧几里得算法

1. 前置知识-裴蜀定理

裴蜀定理：$\forall a,b\in \Z$, 令$d=(a,b)$，那么对于任意的整数$x,y\in \Z$，$ax+by=kd$。特别的，一定$\exist x,y$，使得$ax+by=d$成立。

丢番图方程$ax+by=m$有解，当且仅当$m$是$d$的倍数。丢番图方程有解时必然有无穷多个解，每组解$x,y$都称为裴蜀数，可用辗转相除法求得。

证明：

（前半句）$\because d|a,d|b$，$\therefore \forall x,y\in Z, d|(ax+by)$

（特别的…）设$s$为$ax+by$的最小正值，令 $q=\lfloor \frac{a}{s} \rfloor$，$r=a ~mod ~s$。

则$r=a-\lfloor \frac{a}{s} \rfloor\times s=a-q\times(ax+by)=a(1-qx)+b(-qy)$，即$r$也为$a,b$的线性组合

$\because r=a~mod~s$ ，$\therefore 0\leq r <s$

又$s$为$ax+by$的最小正值，可得$r=0$，即$a ~mod~s=0$。

$\therefore s|a$，再设$r_2=b~mod~s$，同理可得$s|b$。因此$s$为$a,b$的公因子，$d\geq s$。

$\because d|a,d|b,s=ax+by$，$\therefore d|s$，$d\leq s$。

因此$d=s$，命题得证。

推论1：$(a,b)=1$的充分必要条件是$\exist x,y\in Z, s.t.~~ax+by=1$。

推论2：裴蜀等式也可以用来给最大公约数定义：$d$其实就是最小的可以写成$ax + by$形式的正整数。

推论2：设$a_1,a_2,...,a_n$为$n$个整数，$d$是它们的最大公约数，那么$\exist x_1,x_2,...,x_n$，使得$a_1x_1+a_2x_2+...+a_nx_n=d$成立。特别的，若$a_1,a_2,...,a_n$是互质的（不是两两互质），那么$\exist x_1,x_2,...,x_n$，使得$a_1x_1+a_2x_2+...+a_nx_n=1$成立。

2. 扩展欧几里得算法

如何用扩展欧几里得算法求裴蜀数？

假如要求解的不定方程（又名丢番图方程）为$ax+by=m$

我们现在先求解不定方程$ax+by=d$，其中$d=(a,b)$，$d|m$。

由欧几里得算法性质1，2可知$(a,b)=(b,a~mod~b)=(b, a-\lfloor \frac{a}{b} \rfloor\times b)$

若$ax_1+by_1=d$有解，则$by_2+(a~mod~b)x_2=d$一定有解，即$by_2+(a-\lfloor \frac{a}{b} \rfloor\times b)x_2=d$有解。

化简得$ax_2+b(y_2-\lfloor \frac{a}{b} \rfloor\times x_2)=d$，那么$x_1=x_2,y_1=y_2-\lfloor \frac{a}{b} \rfloor\times x_2$。

于是可以递归进行操作，当$b'=0$时，$(a',0)=d$，也就是$a'=d$，此时$x=1,y=0$为一组平凡解，再不断带回，即可得到不定方程的一组特解，设此特解为$\{x_1,y_1\}$。则通解即为$\{x_1+k\times\frac{b}{d}, y_1-k\times\frac{a}{d}, k\in \Z\}$

证明通解是方程的解：

$ax+by=a\times(x_1+k\times\frac{b}{d})+b\times(y_1-k\times\frac{a}{d})\\=ax_1+by_1+k\times (\frac{ab}{d}-\frac{ab}{d})=d$

因此，通解是可以使等式成立的。

那么同理，$ax+by=m$，通解也是$\{x_0+k\times \frac{b}{d}, y_0-k\times \frac{a}{d}\}$。

• 代码

int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}

同余

1. 定义

如果$a,b\in\Z$，而$m$是一个固定的正整数，则当$m|(a-b)$时，我们就说$a,b$对模$m$同余，记作$a\equiv b(\mod m)$，当$m$不能整除$a-b$时，我们就说$a,b$对模$m$不同余，记作$a \not\equiv b(\mod m)$。

2. 运算法则

$\begin{cases} A\times B~mod ~P = (A ~mod ~P \times B ~mod ~P) \mod P\\ (A + B)~ mod~ P = (A ~mod ~P + B ~mod ~P) \mod P \\ (A - B)~ mod ~P = (A ~mod~ P - B ~mod ~P + P) \mod P \\ 令cnt(x)=\_\_bulitin\_popcount(x), 则\\ cnt(A \oplus B) ~mod ~2 = cnt(A)~mod 2~ \oplus cnt(B)\mod 2 \\ A\equiv B(mod~P) \rightarrow A^n\equiv B^n \mod m \end{cases}$

3. 基本概念

(1) 剩余类 完全剩余系 和 简化剩余系

• 剩余类：也叫同余类，设模为$n$，则根据余数可将所有的整数分为$n$类，把所有和整数$a$模$n$同余的整数构成的集合叫做模$n$的一个剩余类，记作$[a]$，并把$a$叫做剩余类$[a]$的一个代表元。
• 完全剩余系：从模$n$的每个剩余类中各取一个数，得到一个由$n$个数组成的集合，叫做模$n$的一个完全剩余系。最常用的完全剩余系是$\{0,1,...,n-1\}$。
• 简化剩余系：也称既约剩余系或缩系，是$n$的完全剩余系中与$n$互质的数构成的子集。如果模$n$的一个剩余类里所有数都与$n$互质，就把它叫做与模$n$互质的剩余类。在与模$n$互质的全体剩余类中，从每个类中各任取一个数作为代表组成的集合，叫做模$n$的一个简化剩余系。

4. 常用小定理

• **定理1：**如果$a,b,c$是任意三个整数，$m$是一个正整数且$(m,c)=1$，则当$ac\equiv bc(\mod m)$时，有$a\equiv b(\mod m)$。

证明：由于$c(a-b)=ac-bc=mq$，其中$q\in \Z$，$(m,c)=1$。我们有$a-b=m\frac{q}{c}=mq_1$。

• **定理2：**满足$a^{x}\equiv 1(\mod m)$的最小正整数$x$，一定是$\varphi(m)$的约数，即$x|\varphi(m)$。

反证法。假设$x\not\mid \varphi(m),\varphi(m)=qx+r, r\in(0,x)$。

则有$a^{qx}\equiv 1^q(\mod m)$，$a^{qx+r}\equiv 1(\mod m)$

$a^r\equiv 1(\mod m)$，$r<x$，又$x$是满足同余式的最小正整数，矛盾。得证。

• 定理3：$\exist x>0$，使得$a^x\equiv 1(\mod m)$成立，它的充分必要条件为$(a,m)=1$。

必要性：即欧拉定理$a^{\varphi(m)}\equiv 1(\mod m)$的证明；

充分性：（反证法）若$a^x\equiv 1(\mod m),x>0$，则$a^x+k\times m=1$，若$(a,m)=w>1$，则$a^x+k\times m=w\times\frac{a^x+k\times m}{w}\geq w>1$。矛盾，得证。

同余这块，有非常多乱七八糟的构造方法，非常偏数学，甚至可以做到《初等数论》上的题目……只能说注意积累，大胆乱猜。

初等数论四大定理

1. 威尔逊定理

(1) 结论

当且仅当$p$为素数时，$(p-1)!\equiv -1(\mod p)$。

(2) 证明

充分性：若$p$不为素数，则$(p-1)!\not\equiv -1(\mod p)$。

• 当$p=4$时，显然$(p-1)!\equiv 6\equiv 2(\mod p)$；

• 当$p>4$时

  • $p$为完全平方数，则$\exist k$，使得$p=k^2$，由于$p>4$，故$k>2,2k<p$，$(p-1)!\equiv n(k\times2k)\equiv 2n\times k^2\equiv 0(\mod p)$。
  • $p$不是完全平方数，则$\exist a,b,a\neq b$，使得$ab=p$，则$(p-1)!\equiv nab\equiv 0(\mod p)$。

必要性：若$p$为素数，则一定有$(p-1)!\equiv -1(\mod p)$。

$p=2$时，结论显然成立。

若$p$为奇素数，取集合$A=\{1,2,3,..,p-1\}$，$A$构成模$p$乘法的简化剩余系，即$\forall i\in A,\exist j\in A$，使得$i\times j\equiv 1(\mod p)$。

证明：因为$A$构成模$p$乘法的取值的集合了（除了0），所以这个结论肯定成立。

那么，这$p-1$个数是不是两两配对的呢？首先，由同余的运算法则，可以得到一定没有$ij\equiv ik(\mod p), j\neq k$的情况，那么它一定是两个一对，或者单独一个的情况。考虑$x^2\equiv 1(\mod p)$，解得$x\equiv 1(\mod p)$，或者$x\equiv p-1(\mod p)$，那么其余则两两配对。因此$(p-1)!\equiv 1\times (p-1)\equiv -1(\mod p)$，得证。

(5)例题

可以看下它的考察方式：UVA1434 YAPTCHA，主要就是欧拉筛+威尔逊定理+前缀和

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, cnt;
const int N = 3e6 + 20;
bool st[N];
int p[N], pre[N];

void Euler(int n){
	for (int i=2;i<=n;++i){
		if (!st[i]) p[++cnt] = i;
		for (int j=1;p[j]<=n/i;++j){
			st[i * p[j]] = true;
			if (i % p[j] == 0) break;
		}
	}
}

void init(){
	Euler(N - 1);
	for (int i=1;i<N;++i){
		int x = 0;
		if (i > 7 && (i - 7) % 3 == 0 && !st[i]){
			x = 1;
		}
		pre[i] = pre[i - 1] + x;
	}
}

int main(void){
	init();
	int t;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		printf("%d\n", pre[n * 3 + 7]);
	}
	return 0;
}

2. 欧拉定理

(1) 结论

若$m$是一个大于1的整数，且满足条件$(a,m)=1$，则我们有

$a^{\varphi(m)}\equiv 1(\mod m)$

(2) 证明

引理1： 设$m$是一个大于1的整数，$a$是一个整数且满足$(a,m)=1$，如果$B=\{b_1,b_2,..,b_{\varphi(m)}\}$是模$m$的一个简化剩余系，则$B'=\{ab_1,ab_2,..,ab_{\varphi(m)}\}$也是模$m$的一个简化剩余系。

证明：由于从$B$中取出任何一个正整数$b_i$，都有$(b_i,m)=1$。又$(a,m)=1$，可以得到在$B'$中任意取出一个整数$ab_i$，都有$(ab_i,m)=1$。那么，现在利用反证法，假设在$B'$中存在两个整数$ab_k,ab_{\lambda}$，$1\leq k < \lambda \leq \varphi(m)$，使得：$ab_k\equiv ab_{\lambda}(\mod m)$成立。

又$(a,m)=1$，故$b_k\equiv b_{\lambda}(\mod m)$，由于$b_k,b_{\lambda}$是简化剩余系的元素，因此不可能模$m$同余，所以同余等式不可能成立，得证。

下面正式的证明欧拉定理。

考虑模$m$的最小正缩系$A$，即$A=\{1,a_2,...,a_{\varphi(m)}\}$，是不大于$m$且和$m$互质的全体正整数，令$r_1$是一个整数，满足条件：$ a \times 1\equiv r_1(\mod m), r_1\in[0,m-1]$

令$r_i$（其中$i=2,..,\varphi(m)$）是一个整数，满足条件：$aa_i\equiv r_i(\mod m),r_i\in[0,m-1]$。

则我们有$a\equiv r_1(\mod m),aa_2\equiv r_2(\mod m),..,aa_{\varphi(m)}\equiv r_{\varphi(m)}(\mod m)$

由于$A$是模$m$的一个简化剩余系，并且$(a,m)=1$，因此$R=\{r_1,r_2,..,r_{\varphi(m)}\}$也是一个简化剩余系，并且和$A$至少在次序上可能有不同，故得到$\prod_{i=1}^{\varphi(m)}r_i=\prod_{i=1}^{\varphi(m)}a_i$

因此$\prod_{i=1}^{\varphi(m)}(a\times a_i) \equiv \prod_{i=1}^{\varphi(m)}a_i (\mod m)$

即$a^{\varphi(m)}\equiv 1(\mod m)$。

(3) 推论

欧拉降幂：

• $A^b\equiv A^{b\mod \varphi(m)} (\mod m)$

证明：设$b=k\times \varphi(m)+r$，则$r=b\mod \varphi(m)$。

$A^b\equiv A^r\times (A^{\varphi(m)})^k\equiv A^r(\mod m)$，得证。

3. 费马小定理

(1) 结论

事实上，费马小定理就是欧拉定理的一种特殊情况。

如果$p$为质数，$p\nmid a$，则我们有$a^{p-1} \equiv 1 (\mod p)$

(1) 证明

由于$p$为质数，因此$\varphi(p)=p-1$，取欧拉定理中$m=p$，即得到费马小定理。

需要注意的是，$\exist m\in \N^+,a\in \Z$，使得$m \nmid a$，这里$m$不是素数，使得$a^{m-1}\equiv 1(\mod m)$，即费马小定理的逆定理不成立。比如，$1024\equiv 1(\mod 341)$，$2^{340}\equiv (2^{10})^{34}\equiv (1024)^{34}\equiv 1(\mod 341)$，而$341=11\times 31$，不是素数。

(2) 推论

明显的，当$p$为质数，且$p \nmid a$时，$a^{p-2}\equiv a^{-1} (\mod p)$，由此就可以求得在模$p$意义下的乘法逆元。

欧拉定理和费马定理很难单独考察，大部分都是作为解题的一个步骤出现。

4. 中国剩余定理

1) 中国剩余定理(crt)

定理：

有一元线性同余方程组$(S)$如下。

$(S):\begin{cases} & x\equiv a_1~(\mod m_1) \\ & x\equiv a_2~(\mod m_2) \\ &... \\ & x\equiv a_n~(\mod m_n) \end{cases}$

假设整数$m_1,m_2,...,m_n$两两互质，则对任意的整数$a_1,a_2,...,a_n$，方程组$(S)$有解，并且通解可以用如下方式构造得到：

设$M=\prod \limits _{i=1} ^{n} m_i$，$M_i=\frac{M}{m_i}$，设$t_i=M_i^{-1}$，为$M_i$在模$m_i$意义下的$M_i$的模$m_i$乘法逆元。

方程组$(S)$的通解形式为$x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nM_n+kM=kM+\sum\limits_{i=1}^na_it_iM_i, k\in \Z$。

在模$M$的意义下，方程组$(S)$只有一个解：$x=(\sum\limits_{i=1}^na_it_iM_i)\mod M$

namo 首先解的每一项，都是可以求出来的，$t_i$也可以通过扩展欧几里得算法求出。然后再来小小的证明下！

证明：

1. 首先证明$x$是方程组$(S)$的一个解。

对于解的每一项，可以看出$a_it_iM_i\equiv a_i\times 1 \equiv a_i(\mod m_i~)$，

$a_it_iM_i\equiv 0~(\mod m_j~)$，$\forall j\in[1,n], j\neq i$

因此，$x$满足$x=a_it_iM_i+\sum\limits _{j\neq i}a_jt_jM_j \equiv a_i+\sum\limits _{j\neq i}0 \equiv a_i~(\mod m_i), ~~\forall i\in[1,n]$

故$x$是方程组的一个解。

2. 然后证明在模$M$的意义下，方程组$(S)$只有一个解。

假设$x_1,x_2$都是方程组$(S)$的解，那么$x_1-x_2\equiv 0~(\mod m_i), \forall i\in [1,n]$

而$m_1,m_2,...,m_n$两两互质，这说明$M|(x_1-x_2)$，所以方程组$(S)$的任何两个解之间必然相差$M$的整数倍，所以方程组所有的解的集合就是$\{kM+\sum \limits _{i=1} ^n a_it_iM_i;k\in \Z\}$

所以在模$M$的意义下，方程组$(S)$只有一个解。

• 代码：

int n;
const int N = 10 + 5;
int A[N], B[N];

ll mod(ll a, ll b){
	return (a % b + b) % 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, y, x);
	y -= a / b * x;
	return d;
}

int main(void){
	scanf("%d", &n);
	ll M = 1, res = 0, ti, y;
	for (int i=1;i<=n;++i){
		scanf("%d%d", &A[i], &B[i]);
		M = M * A[i];
	}
	for (int i=1;i<=n;++i){
		ll Mi = M / A[i];
		exgcd(Mi, A[i], ti, y);
		res = mod(res + Mi * ti * B[i], M);
	}
	printf("%lld\n", res);
	
	return 0;
}

2) 扩展中国剩余定理(excrt)

（rxz的题解写的太好了，受益良多QAQ，他讲的东西真的都是清晰细致又简单 但是因为他用python所以不推mod 岂可修）

https://www.luogu.com.cn/blog/blue/kuo-zhan-zhong-guo-sheng-yu-ding-li

这里自己再重新推导一遍。

修改条件，使得$m_1,m_2,...,m_n$不再两两互质，此时应该如何求方程组的解？

$(S):\begin{cases} & x\equiv a_1~(\mod m_1) \\ & x\equiv a_2~(\mod m_2) \\ &... \\ & x\equiv a_n~(\mod m_n) \end{cases}$ $x=\{kM+\sum \limits _{i=1} ^n a_it_iM_i;k\in \Z\}$

互质条件不满足时，$t_i$不存在。（回忆逆元的定义，只有当$(b,m)=1$时才存在$b^{-1}(\mod m)$），那么不能利用公式时，只能尝试去不断的合并方程，直到$n$个方程仅剩下一个，再使用扩展欧几里得算法求解唯一的同余方程。那么，如何将两个方程等价的变换为一个方程呢？考虑如下情况：

$\begin{cases} & x\equiv a_1(\mod m_1) \\ & x\equiv a_2(\mod m_2)\end{cases}$

此方程组等价于$x = k_1m_1+a_1=k_2m_2+a_2$

移项后，得$k_1m_1-k_2m_2=a_2-a_1$。

令$a=m_1,b=m_2,m=a_2-a_1$，方程就变成了我们最熟悉的不定方程。那么，记$d=(m_1,m_2)$，求是否有$x,y$，满足$ax+by=d$。求解的步骤即是：先用裴蜀定理判断是否有解，再用扩展欧几里得算法求解（系）。则$k_1=x\times \frac{a_2-a_1}{d},k_2=-y\times \frac{a_2-a_1}{d}$，这就是方程的一组特解。为了避免数据溢出，可以让$k_1:=k_1 \mod \frac{m_2}{d}$（具体证明见裴蜀定理），那么，$x=a_1+k_1m_1$，就求出来了两个方程的特解。设这个特解为$r$，那么它的通解就是$\{r+k\times LCM, k\in \Z\}$，那么，就可以合并两个同余方程啦！

$x\equiv r~(\mod LCM)$

这样不断合并，直到只剩下一个方程，解出答案即可。注意，中间非常容易数据溢出！即使是long long！所以最好直接用一个mul函数，一边做乘法一边做模运算。

---

横线中的这段是rxz的证明，嘛嘛，就相当于方程$ax+by=d$两边$\div d$，结果是一样的。

那么，记$d=(m_1,m_2)$，$p_1=\frac{m_1}{d}, p_2=\frac{m_2}{d}$，易得$(p_1,p_2)=1$。

方程可被写为这样的形式：$k_1p_1-k_2p_2=\frac{a_2-a_1}{d}$

由于当$d|(a_2-a_1)$时，方程才有解，因此右边的式子为整数。接着按照exgcd的流程走，我们求这个方程的解

$\lambda_1p_1+\lambda_2p_2=1$，则$\begin{cases} & k_1=\frac{a_2-a_1}{d} \times \lambda_1\\ & k_2=\frac{a_2-a_1}{d} \times \lambda_2\end{cases}$

将结果代入方程，得$x=a_1+k_1m_1=a_1+\frac{a_2-a_1}{d}\lambda_1m_1$。

这个$x$就是方程的一个特解。

那么，进一步的，如何求出整个解系呢？

**定理：**若有特解$x'$，令$LCM=lcm(m_1,m_2)$，则$\begin{cases} & x\equiv a_1(\mod m_1) \\ & x\equiv a_2(\mod m_2)\end{cases}$ 的通解为$x=\{k\times LCM+x';k\in \Z\}$。

该定理的证明和CRT的证明完全相同。好累，我不想重抄一遍所以就这样吧

---

• 代码：

int n;
const int N = 1e5 + 10;
ll a1, m1, a[N], m[N], res;

ll mul(ll a, ll b, ll M){
    ll res = 0;
    while (b > 0){
        if (b & 1) res = (res + a) % M;
        a = (a + a) % M;
        b >>= 1;
    }
    return res;
}

ll merge(ll a2, ll m2){
    ll x, y, M, c = mod(a2 - a1, m2);
    ll d = exgcd(m1, m2, x, y);
    if (c % d){
        return -1;
    }
    M = (m1 / d * m2);
    ll k1 = mod(mul(x, c / d, m2 / d), m2 / d);
    ll r = mod(k1 * m1 + a1, M);
    a1 = r, m1 = M;
    return r;
}

int main(void){
    scanf("%d", &n);
    scanf("%lld%lld", &m1, &a1);
    if (n == 1){
        printf("%lld\n", mod(a1, m1));
        return 0;
    }
    for (int i=1;i<n;++i){
        scanf("%lld%lld", &m[i], &a[i]);
    }
    for (int i=1;i<n;++i){
        res = merge(a[i], m[i]);
        if (res < 0) break;
    }
    printf("%lld\n", res);
    return 0;
}

高斯消元解线性方程组

这一部分的原理参考线性代数即可。

• 步骤

1. 枚举每一列$c$
   • 找到绝对值最大的一行，将该行换到最上面；
   • 将该行第1个数变成1，将下面所有行的第$c$列消成0；

• 时间复杂度：对于一个有$n$个未知数，有$n$个方程的方程组，时间复杂度为$O(n^3)$
• 代码

(1) 浮点数版

#define ZERO 1e-8

int n;
const int N = 100 + 10;
double a[N][N]; // 增广矩阵 

void printA(){
	for (int i=0;i<n;++i){
		for (int j=0;j<n+1;++j){
			printf("%.2lf ", a[i][j]);
		}
		puts("");
	}
	puts("");
}

// 高斯消元, 答案存于a[i][n]中, i:[0,n) 
int gauss(){
	int c = 0, r = 0;
	for (c=0;c<n;++c){
		int t = r; // 找绝对值最大的行 
		for (int i=r;i<n;++i){
			if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
		}
		if (fabs(a[t][c]) < ZERO) continue;
	
		for (int i=c;i<=n;++i) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到顶端 
		for (int i=n;i>=c;--i) a[r][i] /= a[r][c]; // 将当前行的首位变成1 
		for (int i=r+1;i<n;++i){ // 用当前行将下面所有的列消成0 
			if (fabs(a[i][c]) > ZERO){
				for (int j=n;j>=c;--j){
					a[i][j] -= a[r][j] * a[i][c];
				}
				// printA();
			}
		}
		++r;
	}
	if (r < n){
		for (int i=r;i<n;++i){
			if (fabs(a[i][n]) > ZERO){
				return 2; // 无解 
			}
		}
		return 1; // 有无穷多解 
	}
	for (int i=n-1;i>=0;--i){
		for (int j=i+1;j<n;++j){
			a[i][n] -= a[i][j] * a[j][n];
		}
	}
// 	printA();
	return 0;
}

int main(void){
	scanf("%d", &n);
	for (int i=0;i<n;++i){
		for (int j=0;j<n+1;++j){
			scanf("%lf", &a[i][j]);
		}
	}
	int t = gauss();
	if (t == 2){
		puts("No solution"); return 0;
	}
	else if (t == 1){
		puts("Infinite group solutions"); return 0;
	}
	for (int i=0;i<n;++i){
		if (fabs(a[i][n]) < ZERO) a[i][n] = 0;
		printf("%.2lf\n", a[i][n]);
	}
	return 0;
}

(2) 异或版

int n;
const int N = 100 + 10;
int a[N][N];

int gauss(){
    int c = 0, r = 0;
    for (c=0;c<n;++c){
        int t = r;
        for (int i=r;i<n;++i){
            if (a[i][c] == 1){
                t = i;break;
            }
        }
        if (a[t][c] == 0) continue;

        for (int i=0;i<n+1;++i) swap(a[t][i], a[r][i]);
        for (int i=r+1;i<n;++i){
            if (a[i][c] > 0){
                for (int j=n;j>=c;--j){
                    a[i][j] ^= a[r][j];
                }
            }
        }
        ++r;
    }

    if (r < n){
        for (int i=r;i<n;++i){
            if (a[i][n]) return 2;
        }
        return 1;
    }
    for (int i=n-1;i>=0;--i){
        for (int j=i+1;j<n;++j){
            a[i][n] ^= (a[i][j]*a[j][n]);
        }
    }
    return 0;
}

int main(void){
    scanf("%d", &n);
    for (int i=0;i<n;++i){
        for (int j=0;j<n+1;++j){
            scanf("%d", &a[i][j]);
        }
    }
    int t = gauss();
    if (t == 1){
        puts("Multiple sets of solutions"); return 0;
    }
    if (t == 2){
        puts("No solution"); return 0;
    }
    for (int i=0;i<n;++i) printf("%d\n", a[i][n]);

    return 0;
}

容斥原理

假如有一个Venn图，包含四个集合$S_1,S_2,S_3,S_4$，求$S_1\bigcup S_2\bigcup S_3\bigcup S_4$中包含元素的个数，则：

\begin{align} & |S_1\bigcup S_2\bigcup S_3\bigcup S_4| \\ &=|S_1|+|S_2|+|S_3|+|S_4| \\ & -|S_1\bigcap S_2|-|S_1\bigcap S_3|-|S_1\bigcap S_4|-|S_2\bigcap S_3|-|S_2\bigcap S_4|-|S_3\bigcap S_4| \\ & +|S_1\bigcap S_2\bigcap S_3|+|S_1\bigcap S_2\bigcap S_4|+|S_2\bigcap S_3\bigcap S_4| \\ & -|S_1\bigcap S_2\bigcap S_3\bigcap S_4| \end{align}

那么对于$n$个集合的并，每一项若为奇数个集合的交，则为正，若是偶数个集合的交则为负，然后相加。显然，这个式子一共有$2^n-1$项。

设$B=\{S_1,S_2,...,S_n\}$，则

$|\bigcup\limits^n_{i=1}S_i |=\sum\limits _{C\subseteq B}(-1)^{|C|-1}|\bigcap\limits _{e\in C}e|$

这个公式概率论也可以用哦！$S_i$就表示$i$事件发生的概率

时间复杂度：$O(2^n)$。

严格证明：呃呃好累，来辆车创死我吧

要证明容斥定理是正确的，就等价于证明在集合$S_i$中的任一元素，都在右边的等式中被计算了正好一次。

假设元素$x$出现在了$k$个$S_i$集合中，$k\in[1,n]$

当$|C|=1$时，$x$被加了$k$次，当$|C|=2$时，$x$被减了$C_k^2$次；

……

当$|C|=k$时，$x$被加了$(-1)^{k-1}C_k^k$次。

那么，元素$x$总共被计算了$T=C_k^1-C_k^2+...+(-1)^{i-1}\times C_k^i+...+(-1)^{k-1}\times C_k^k$次

由二项式定理，可知$(1-a)^k=C_k^0\times a^0-C_k^1\times a^1+...+(-1)^k\times C_k^k\times a_k$，

令$a=1$，则$(1-1)^k=C^0_k\times1^0-T$，即$T=1-0=1$，得证。

一个不算模板的模板，求$1$~$n$之间能被$p[m]$数组中任一元素整除的数的个数。代码：

int n, m;
const int M = 16 + 5;
int p[M];

int main(void){
	scanf("%d%d", &n, &m);
	for (int i=0;i<m;++i) scanf("%d", &p[i]);
	
	int res = 0;
	for (int i=1;i<1<<m;++i){  // 枚举(2^n)-1种情况
		int t = 1, s = 0;
		for (int j=0;j<m;++j){ // 枚举m位
			if ((i>>j) & 1){
				if ((ll)t * p[j] > n){
					t = -1; break;
				}
				t *= p[j];
				++s;
			}
		}
		if (t > 0){
			if (s%2) res += n / t;
			else res -= n/t;
		}
	}
	printf("%d\n", res);
	
	return 0;
}

常见数

俺觉得学常见数，更多的可以说是借着常见数来学习如何推公式，以及其中dp状态转移的化简，对子问题的划分xd

1.卡特兰数(Catalan Number)

捏麻麻地 卡特兰数 奥妙无穷

ps：这篇博客说的应用非常好，但是太多了，贴个链接

https://zhuanlan.zhihu.com/p/31317307

(1) 定义：

设卡特兰数的第$n$项为$h(n)$，$h(0)=1,h(1)=1$。catalan数满足递推式：

$h(n)=h(0)\times h(n)+h(1)\times h(n-1)\times ...\times h(n-1)\times h(0)$，$n\geq 2$

此时递推关系的解为$h(n)=\frac{C_{2n}^n}{n+1}$

另类递推式：$h(n)=h(n-1)\times \frac{4n-2}{n+1}$，或者说$h(n+1)=h(n)\times \frac{4n+2}{n+2}$

递推关系的另类解为$h(n)=C_{2n}^n-C_{2n}^{n-1}$。

事实上，它们都是等价的。（这些递推式还是挺容易证明的就不写了，敲公式好累）

以防一时看不出来，记一下前几项（误）（从第0项开始）

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452

(2) 应用

• 出栈次序

题目见AcWing415，相当于问一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列。

对于每一个$h(k)$，我们都可以把它的每个进出栈的过程看成独立的，然后枚举分割的方案，那么$h(k)=h(0)\times h(k-1)+...+h(n-1)\times h(0)$。（我知道我讲的不好，但是意会一下QAQ）

或者这么想，对于每个数来说，必须进栈一次，出栈一次。把进栈设置为状态0，出栈设为1。那么，$n$个数的所有状态对应$n$个1和$n$个0组成的长度为$2n$的序列。显然，无论何时，进栈的数量都不小于出栈的数量，这个问题就转换成了AcWing889（我在刷题有详细写解法）

类似的还有买票找零问题，有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。

• 凸多边形三角划分

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。给定凸多边形的边数$n$，求不同划分的方案数$f(n)$​。嗯……lcy讲过这个来着，but我还是贴一下百度百科的证明吧（捂脸）

因为凸多边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准，以这条边的两个顶点为起点$P_1$和终点$P_n$，将该凸多边形的顶点依序标记为$P_1,P_2,...,P_n$，再在该凸多边形中找任意一个不属于这两个点的顶点$P_k,2\leq k \leq n-1$，来构成一个三角形，用这个三角形把一个凸多边形划分成两个凸多边形，其中一个凸多边形，是由$P_1,P_2,...,P_k$构成的凸$k$边形（顶点数即是边数），另一个凸多边形，是由$P_k,P_{k+1},...,P_n$构成的凸$n-k+1$边形。

此时，我们若把$P_k$视为确定一点，那么根据乘法原理，$f(n)$的问题就等价于——凸$k$多边形的划分方案数乘以凸$n-k+1$多边形的划分方案数，即选择Pk这个顶点的$f(n)=f(k)×f(n-k+1)$。而$k\in[2,n-1]$，所以再根据加法原理，将k取不同值的划分方案相加，得到的总方案数为：$f（n）=f(2)f(n-2+1)+f(3)f(n-3+1)+…+f(n-1)f(2)$。也就是说，$f(n)=h(n-2)$。

• 给定节点组成满二叉树

有$n+1$个叶子节点的满位置二叉树（即每个节点有0或2个子节点，且左子节点和右子节点是不同的）的计数问题，相当于有$n$个内节点的满位置二叉树的计数问题。

这道题，我还是和凸多边形划分相同的思路，可以发现，这些应用都有一个共同的特点，就是可以通过一次分割，划分为两个完全一致只是规模变小的子问题，并且，这两个子问题完全独立，那么所得方案数就可以通过乘法原理相乘，再枚举分割方法，根据加法原理把它们相加。

博客提供了一个很特别的思路。

• 长方形填充阶梯形状

• n对括号正确匹配数目, Young表问题, 不相交的弦, 笔画群峰, 不出现312模式的全排列

这些都是很经典的问题，但是太多了写不下~~（不想写）~~，可以自己看我上面的链接哦，我觉得值得一看！特别是全排列和young表

2. 斐波那契数

(1) 定义：

递推式：$F_0=0,F_1=1$，$F_n=F_{n-1}+F_{n-2}$，$n\geq3,n\in \N$。

通项公式：$F_n=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n+(\frac{1-\sqrt 5}{2})^n]$

（通项公式就是用待定系数法搞成等比数列然后组合证明出来的，可以看https://www.cnblogs.com/1024th/p/10902775.html这个博客，这里简单说一下另一种方式）

显然可以构造等比数列$C_n=F_n-aF_{n-1}$，那么$F_n-aF_{n-1}=b(F_{n-1}-aF_{n-2})$，代入递推式就可以解出来$a,b$的值，得到$C_n=b^{n-1}$，则$F_n=b^{n-1}+aF_{n-1}$，这样就把二阶递推式化成了一阶递推式，然后再做一次待定系数法，$F_n+kb^n=-a(F_{n-1}+kb^{n-1})$，然后不停化简，得到$k$的式子，再把$a,b$两组解的任何一组代进去（两组解结果一样的），就得到了$F_n=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n+(\frac{1-\sqrt 5}{2})^n]$。这个通项公式有叫“比内公式”，是无理数表示有理数的一个范例。

(2) 相关恒等式：

（证易，敲累，简写，博客有多处笔误，按俺的公式来）

• $\sum\limits _{i=1}^n F_i=F_{n+2}-F_2=F_{n+2}-1$

证明：$F_1+F_2+F_3+...=F_3-F_2+F_4-F_3+...=F_{n+2}-F_2$

• $F^2_1+F^2_2+⋯+F^2_n=F_nF_{n+1}$

证明：$F_nF_{n+1}=F_n(F_{n-1}+F_n)=F_n^2+F_{n-1}(F_{n-2}+F_{n-1})=...=\sum\limits _{i=1}^n F_i^2$

• $F_1+F_3+F_5+...F_{2n-1}=F_{2n}$

证明：$F_{2n}=F_{2n-1}+F_{2n-2}=F_{2n-1}+F_{2n-3}+F_{2n-4}+...=F_1+F_3+...+F_{2n-1}$

• $F_2+F_4+F_6+...+F_{2n}=F_{2n+1}-F_1=F_{2n+1}-1$

证明：和上一个恒等式一模一样属于是

• $F_n=F_mF_{n-m+1}+F_{m-1}F_{n-m}$

证明：数学归纳法

当$m=2$时，$F_n=F_2F_{n−2+1}+F_{2−1}F_{n−2}=F_{n−1}+F_{n−2}$成立。

设当$m=k(2≤k≤n−2)$时，$F_n=F_kF_{n−k+1}+F_{k−1}F_{n−k}$成立。
$ \begin{align} & F_n=F_kF_{n−k+1}+(F_{k+1}−F_k)F_{n−k}\ &=F_{k+1}F_{n-k}+F_k(F_{n-k+1}-F_{n-k})\ & =F_{k+1}F_{n-k}+F_kF_{n-k-1} \end{align}$

即$m=k+1$时等式依旧成立，得证。

• $F_{n-1}F_{n+1}=F_n^2+(-1)^n$

数学归纳法，假设$F_{n-1-1}F_{n-1+1}=F_{n-1}^2+(-1)^{n-1}$成立

$(F_{n}-F_{n-2})(F_n+F_{n-1})=F_n^2+(-1)^n$

$\Leftrightarrow F_n^2+F_nF_{n-1}-F_{n-2}F_n-F_{n-2}F_{n-1}=F_n^2+(-1)^n$

$\Leftrightarrow F_{n-1}(F_n-F_{n-2})-F_{n-2}F_{n}=(-1)^n$

$\Leftrightarrow -F_{n-2}F_n=-F_{n-1}^2+(-1)^n$

$\Leftrightarrow F_{n-1-1}F_{n-1+1}=F_{n-1}^2+(-1)^{n-1}$，得证

(3) 性质：

• 相邻项互质

证明：$(F_n,F_{n-1})=(F_{n-1},F_n-F_{n-1})$，不断递归，$(F_2,F_1)=1$。

• $gcd(F_n,F_m)=F_{gcd(n,m)}$

证明：$(F_n,F_m)=(F_mF_{n-m+1}+F_{m-1}F_{n-m}, F_m), n>m$

又$(a,b)=(a-kb,b)$，所以$(F_n,F_m)=(F_{m-1}F_{n-m},F_m)$

因为相邻项互质，所以$F_{m-1},F_m$没有公因子，因此$(F_n,F_m)=(F_{n-m},F_m)$

不断递归下去，可得$(F_n,F_m)=(F_{n\mod m},F_m)$

交换$m,n \mod m$的位置，一直做下去，我超 是你，欧几里得！得证。

• $n|m,F_n|F_m$

相当于性质2的特例。

(4) 计算方法

参见yxc的求解斐波那契数列的若干方法。

在此之外，补充另一种利用性质计算的方法：快速倍增法

(5) 应用

有些奇奇怪怪的组合数，化到最后是斐波那契和其他式子的组合，可以说是非常神奇（指我不会）记得cf有一题D？算灯塔方案，就用到了斐波那契数列

排列问题

康托展开

1. 不重复元素的康托展开

对于一个从1到$n$的排列$\{a_1,a_2,...,a_n\}$，比它小的排列的数量为：$\sum\limits_{i=1}^n (s_i\times(n-i)!)$

其中，$s_i$为在$a_i$元素后面的所有元素中，小于$a_i$的元素个数。

简单的说下证明：假设当前到了第$i$位元素，那么前面$i-1$位不变，把比$a_i$小的元素拿到$a_i$的位置，剩下的元素随便取，那么答案就是$(n-i)!$个，得证。有点数位dp的那个意思。namo 怎么查询比$a_i$更小的元素呢？树状数组鸭wwwww

2. 可重复元素的康托展开

这个首先就要知道有重复元素的全排列个数的计算公式，$n$个元素被分成$k$类，每类中元素的值相同，且第$i$类的元素个数为$a_k$个，则这$n$个元素的全排列数为$\frac{n!}{\prod_{i=1}^{k}(a_k!)}$。

然后，剩下的思路和不重复元素的康托展开是一样的，数位dp+树状数组即可。

数据范围：$n\leq 50$；答案在long long范围内。

#include<cstdio>
using namespace std;
#define ri register int
#define ll long long
ll ans,c[55][55];
int a[10],len,n[55],cnt;
ll multiqpl(int a[],int l)
{
    ll res=1;
    for(ri i=0;i<=9;i++)
    {
        res*=c[l][a[i]];
        l-=a[i];
    }
    return res;
}
int main()
{
    for(char ch=getchar();ch>='0'&&ch<='9';ch=getchar())a[n[++len]=ch-48]++;
    c[0][0]=1;
    for(ri i=1;i<=len;i++)
    {
        c[i][0]=c[i][i]=1;
        for(ri j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    for(ri i=1;i<=len;i++)
    {
        cnt=0;
        for(ri j=0;j<n[i];j++)
            if(a[j])
            {
                a[j]--;//将j放到第i位上
                ans+=multiqpl(a,len-i);
                a[j]++;//将j拿走，换下一个
            }
        a[n[i]]--;
    }
    printf("%lld",ans);
}

树形结构

边权均为1的树的直径

• 任取一点作为起点，找到距离该点最远的一个点$u$（DFS or BFS）
• 再找到距离$u$最远的一点$v$（DFS Or BFS）
• 那么$u,v$之间的路径就是一条直径

**证明：**在无根树中，假设树的直径为$bc$，以任意结点$a$为根，得到距离$a$最远的点为$u$。

• 情况1：$au$和$bc$的交点为$x$。

  此时可以得到，$|ux| \geq |cx|$，因此，$|bx|+|ux| \geq |bx|+|cx|$，即$|bu|\geq |bc|$，因此，$u$一定是直径的一个端点；

• 情况2：$bc$和$au$没有交点，那么一定存在路径$xy$，使得$xy$与$au,bc$相交。由于$u$是离$a$最远的点，那么$|ux| \geq |xy|+|cy|$，因此$|by|+|xy|+|ux|\geq |by|+|cy|$，因此，$u$一定是直径的一个端点。

边权不含负数

不含负数时，证明方法是和第一种情况同理的，此时可以用上面的方案来处理。

可以用两遍dfs()，或者使用树形DP。

• 两次DFS的做法

int n;
const int N = 1e4 + 10;
int dis[N];
struct node{
    int v;int w;
};
vector<node> ve[N];

void dfs(int u, int pre){
    for (node i : ve[u]){
        if (i.v == pre) continue;
        dis[i.v] = dis[u] + i.w;
        dfs(i.v, u);
    }
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    int u, v, w, t, res;
    for (int i=1;i<n;++i){
        cin >> u >> v >> w;
        ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
    }
    dis[1] = 0;
    dfs(1, 0);
    t = -1, res = -1;
    for (int i=1;i<=n;++i){
        if (dis[i] > res){
            res = dis[i], t = i;
        }
    }
    dis[t] = 0;
    dfs(t, 0);
    t = -1, res = -1;
    for (int i=1;i<=n;++i){
        if (dis[i] > res){
            res = dis[i], t = i;
        }
    }
    printf("%d\n", res);

    return 0;
}

边权任意（有正有负）

需要用到树形DP。因为在这种情况下，证明将失效。

比如，假如$xy$的长度为负数，那么$|ux| \geq |xy|+|cy|$的条件，将无法推出$|by|+|xy|+|ux|\geq |by|+|cy|$，因为不能保证$|ux|\geq |cy|-|xy|$。

此时，将状态定义为：$f[i]:$两条路径挂载的最高点为$i$时，最长的两点间距离。方法1，是直接用最长距离$d1$和次长距离$d2$来更新答案。

int n, ans;
const int N = 1e4 + 10;
int f[N];
struct node{
    int v;int w;
};
vector<node> ve[N];

int dfs(int u, int pre){
    int dis = 0;
    int d1 = 0, d2 = 0;
    for (node i : ve[u]){
        if (i.v == pre) continue;
        int d = dfs(i.v, u) + i.w;
        dis = max(dis, d);
        if (d >= d1){
            d2 = d1, d1 = d;
        }
        else if (d > d2) d2 = d;
    }

    ans = max(ans, d1 + d2);
    return dis;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    int u, v, w;
    for (int i=1;i<n;++i){
        cin >> u >> v >> w;
        ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
    }

    dfs(1, 0);
    printf("%d\n", ans);

    return 0;
}

方法2，就是正统的搞个$f[n]$来记录答案。（不过其实是一个意思）

int n, ans;
const int N = 1e4 + 10;
int f[N];
struct node{
	int v;int w;
};
vector<node> ve[N];

void dfs(int u, int pre){
	for (node i : ve[u]){
		if (i.v == pre) continue;
		dfs(i.v, u);
		ans = max(ans, f[u] + f[i.v] + i.w);
		f[u] = max(f[u], f[i.v] + i.w);
	}
}

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	int u, v, w;
	for (int i=1;i<n;++i){
		cin >> u >> v >> w;
		ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
	}
	
	dfs(1, 0);
	printf("%d\n", ans);
	
	return 0;
}

求树的中心

（有正有负的情况）

最直白的想法，就是把每个点离它最远的点求出来，然后比较找到最小值，正解也确实是这样。那么对于结点$i$，就有两种可能：一是向下走遇到最远点（此时最远点为i的孩子）；
二是向上走（可能先向上走再向下走）遇到最远点（此时最远点不是它的孩子）。

因此，进行两次树形DP，先求出

$down[i]:$以$i$为两条路径的最高点，求最长路径和次长路径，以及最长路径所在的子节点;

再求出$up[i]:$从$i$开始向上走，离最远点的距离;

int n;
const int N = 1e4 + 10;
struct dist{
	int d1, d2, inx;
};
dist down[N];
struct node{
	int v, w;
};
vector<node> ve[N];
int up[N], f[N];

int dfs(int cur, int pre){
	int d1 = 0, d2 = 0, inx = 0;
	for (node i : ve[cur]){
		if (i.v == pre) continue;
		int d = dfs(i.v, cur) + i.w;
		if (d > d1){
			inx = i.v, d2 = d1, d1 = d;
		}
		else if (d > d2){
			d2 = d;
		}
	}
	down[cur] = dist{d1, d2, inx};
	return d1;
}

void dp(int cur, int pre, int d){
	int inx = down[pre].inx, d1 = down[pre].d1, d2 = down[pre].d2;
	up[cur] = up[pre] + d;
	if (inx == cur){
		up[cur] = max(up[cur], d2 + d);
	}
	else{
		up[cur] = max(up[cur], d1 + d);
	}
	f[cur] = max(up[cur], down[cur].d1);
	for (node i : ve[cur]){
		if (i.v == pre) continue;
		dp(i.v, cur, i.w);
	}
}

int main(void){
	int u, v, w;
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i=1;i<n;++i){
		cin >> u >> v >> w;
		ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
	}

	dfs(1, 0);
	dp(1, 0, 0);

	int res = 1e9 + 10;
	for (int i=1;i<=n;++i){
		res = min(res, f[i]);
	}
	cout << res << endl;
	
	return 0;
}

例题：组合数+树形DP+建虚树

E1 Rubik’s Cube Coloring(easy version)

给结点数为$2^k-1$的完全二叉树染色，一共有6种颜色，限制为：

• 白色不能和白色、黄色相邻；
• 黄色不能和白色、黄色相邻；
• 绿色不能和蓝色、绿色相邻；
• 蓝色不能和蓝色、绿色相邻；
• 红色不能和橘色、红色相邻；
• 橘色不能和红色、橘色相邻；

问有多少种方式，可以给全部节点染色，答案对$10^9+7$取余。

首先，$k=1$，只有一个结点，有6种方式染色；

当$k=2$时，当1号点的颜色固定时，2,3号只能在被ban掉的2种颜色之外，选择一种颜色进行染色，因此答案为$6\times 4\times 4$；

当$k=3$时，当2,3号的颜色固定时，它们的孩子有各16种组合方案，然后再看1号结点固定时，2,3只能在被ben掉的2种颜色之外，选择一种颜色，因此答案为$6\times 4\times 4 \times 16^2$；

因此，若结点数为$2^k-1$，则染色方案有$6\times 16^{2^{k-1}-1}$

也可以写成$6\times 4^{2^{k}-2}$

ll ans, p[63];
const ll MOD = 1e9 + 7;

void init(){
	p[0] = 1;
	for (int i=1;i<63;++i){
		p[i] = p[i-1] + p[i-1];
	}
}

ll qmi(ll m, ll k, ll MOD){
	ll res = 1LL%MOD, t = m;
	while (k){
		if (k & 1) res = res * t % MOD;
		t = t*t % MOD;
		k>>=1;
	}
	return res;
}

int main(void){
	ll k;
	init(); 
	cin >> k;
	ans = qmi(16, p[k-1]-1, MOD);
	ans = (ans*6) % MOD;
	cout << ans << endl;
	
	return 0;
}

E2 Rubik’s Cube Coloring(hard version)

hard version的不同，就在于有些结点，事先指定了颜色，然后问方案数。完全二叉树共有$k$层，指定$n$个结点的颜色，对于接下来的$n$行，每行都有一个$v,s$，$v$代表结点的编号，$s$代表指定结点$v$为$s$颜色，求给完全二叉树染色的方案数，对$10^9 + 7$取模。

• 白色不能和白色、黄色相邻；
• 黄色不能和白色、黄色相邻；
• 绿色不能和蓝色、绿色相邻；
• 蓝色不能和蓝色、绿色相邻；
• 红色不能和橘色、红色相邻；
• 橘色不能和红色、橘色相邻；

数据范围：$1\leq k \leq 60,1\leq n \leq min(2^k-1,2000),1\leq v \leq 2^k-1$。

咳咳，关键词，树 限制 方案数。这不就是一个树形DP嘛！

定义状态$f[i][j]$：结点$i$染成颜色$j$时，以$i$为根的树的方案数量；

那么答案很显然就是：$\sum\limits _{j=1} ^6 f[1][j]$。

准备开写的时候，一个严峻的问题：最多有$2^{60}-1$个结点……那么怎么样能够利用这题的特性做简化呢？

可以看出，1结点被染色之后，它下面的孩子们，就都只剩下4种选法了。对于2,3而言，red, orange显然就被ban了。而对于4,5来说，如果2为剩下四种颜色中的一种，比如2为green，那么对于4,5，green，blue就被ban了。就本例子来说，1下面的孩子们，就共有$4^4$种选法，4为1的孩子的数量。

这样，一个重要的简化就做好了：我们并不需要对整个树进行DP，只需要在这样的树上去做DP：以所有的指定的$n$个结点为叶子，向上找到1（根节点）的树。

比如这样的一颗完全二叉树，我们只需要对1,2,3,5,6,7,10,13这几个结点进行DP就可以了。

解决了数据范围的问题，我们再来看看怎么写转移方程，这个就比较容易了。

假如当前的结点$i$没有被指定颜色，那么$f[i][j] = \sum_{k=1}^4 f[2*i][c]*\sum_{k=1}^4f[2*i+1][c]$；

如果$i$被指定了颜色，那么只有与指定颜色相同的$j$合法，$f[i][j]=1$，其余的$f[i][j]=0$。

设做DP的这些结点的总数为$w$，得到了$res = \sum_{j=1}^6f[1][j]$，之后让$res = res \times 4^{2^k-1-w}$，就是答案。

懒人直接进行一个正义的map。

{% raw %}
#define ll long long 
typedef pair<ll,ll> pll;
#define xx first
#define yy second
#define endl "\n"

int k, n;
const ll MOD = 1e9 + 7;
map<string,int> c = {{"white",1}, {"yellow",2}, {"green",3}, {"blue",4}, {"red",5}, {"orange",6}};
vector<int> edge[7];
map<pll, ll> f;
map<ll, int> def;
set<ll> ms;
ll p[64];

ll qmi(ll m, ll k, ll MOD){
	ll res = 1LL%MOD, t = m;
	while (k){
		if (k & 1) res = res * t % MOD;
		t = t * t % MOD;
		k >>= 1;
	}
	return res;
}

void init(){
	edge[1] = {3, 4, 5, 6}; edge[2] = {3, 4, 5, 6};
	edge[3] = {1, 2, 5, 6}; edge[4] = {1, 2, 5, 6};
	edge[5] = {1, 2, 3, 4}; edge[6] = {1, 2, 3, 4};
	p[0] = 1;
	for (int i=1;i<64;++i){
		p[i] = p[i-1] + p[i-1];
	}
}

ll dfs(ll cur, int color){
	if (f.count(pll(cur, color))){
		return f[pll(cur, color)];
	}
	ll a1 = 0, a2 = 0;
	ll ans = 1;
	if (def.count(cur)){
		if (color!=def[cur]) return 0;
	}
	if (ms.count(cur+cur)){
		for (auto i : edge[color]){
			a1 = a1 + dfs(cur+cur, i) % MOD;
		}
		ans = a1 % MOD;
	}
	if (ms.count(cur+cur+1)){
		for (auto i : edge[color]){
			a2 = a2 + dfs(cur+cur+1, i) % MOD;
		}
		ans = (ans * a2) % MOD;
	}
	
	return f[pll(cur,color)] = ans;
}

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll id; string color;
	init();
	cin >> k >> n;
	for (int i=1;i<=n;++i){
		cin >> id >> color;
		def[id] = c[color];
	}
	for (map<ll,int>::iterator iter = def.begin();iter!=def.end();iter++){
		id = iter->xx;
		while (id!=0){
			ms.insert(id);
			id /= 2;
		}
	}

	ll ans = 0;
	for (int i=1;i<7;++i){
		ans = (ans + dfs(1, i)) % MOD;
	}
	ll exp = (p[k] - 1 - ms.size());
	ll mix = qmi(4, exp, MOD);
	ll res = mix * ans % MOD;
	cout << res << endl;

	return 0;
}
{% endraw %}

例题：树的直径+单调栈/二分

// O(NlogNlogN) 试一下
// 二分+树状数组+枚举
int n, s, len;
const int N = 3e5 + 5;
struct node{
	int id, w;
};
vector<node> ve[N];
vector<int> line;
int fa[N], w[N], dis[N], a[N], tr[N<<1];
bool st[N];

void dfs(int u, int pre){
	fa[u] = pre;
	for (auto to : ve[u]){
		if (to.id == pre) continue;
		dis[to.id] = dis[u] + to.w;
		dfs(to.id, u);
	}
}

void dfs2(int u, int pre, int id){
	for (auto to : ve[u]){
		if (st[to.id] || to.id == pre) continue;
		w[id] = max(w[id], dis[to.id] - dis[id]);
		dfs2(to.id, u, id);
	}
}

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

void update(int x){
	while (x <= len){
		tr[x] = w[line[x]];
		for (int i=1;i<lowbit(x);i<<=1){
			tr[x] = max(tr[x], tr[x - i]);
		}
		x += lowbit(x);
	}
}

int query(int x, int y){
	int res = 0;
	while (y >= x){
		res = max(res, w[line[y]]);
		y--;
		for (;y-lowbit(y)>=x;y-=lowbit(y)){
			res = max(res, tr[y]);
		}
	}
	return res;
}

void solve(){
	n = read(), s = read();
	for (int i=1;i<n;++i){
		int u, v, w;
		u = read(), v = read(), w = read();
		ve[u].push_back(node{v, w}), ve[v].push_back(node{u, w});
	}
	if (n == 1){
		puts("0"); return ;
	}
	int rt = 1, mx, ed, id;
	dfs(1, 0);
	rt = max_element(dis + 1, dis + n + 1) - dis;
	dis[rt] = 0;
	dfs(rt, 0);
	ed = max_element(dis + 1, dis + n + 1) - dis;
	id = ed, mx = dis[id];
	line.push_back(0);
	while (id){
		line.push_back(id), st[id] = true;
		id = fa[id];
	}
	len = line.size() - 1;
	for (int i=1;i<=len;++i){
		dfs2(line[i], 0, line[i]);
	}
	for (int i=0;i<len;++i){
		update(i + 1);
	}
	int res = 1e9 + 7;
	for (int i=1;i<=len;++i){
		int L = i, R = len, mid, ans = -1;
		while (L <= R){
			mid = (L + R) >> 1;
			if (dis[line[i]] - dis[line[mid]] <= s){
				ans = mid;
				L = mid + 1;
			}
			else R = mid - 1;
		}
		int cur = max(dis[line[ans]], dis[ed] - dis[line[i]]);
		cur = max(cur, query(i, ans));
		res = min(res, cur);
	}
	printf("%d\n", res);
}

int main(void){
	int T;
	T = 1;
	while (T--){
		solve();
	}
	
	return 0;
}

礼貌性贴一下单调队列的$O(N)$代码

排序

归并排序

#include <iostream>
using namespace std;
#define ll long long
int n;
const int Max_n = 1e6 + 10;
int a[Max_n], tmp[Max_n];

void merge_sort(int a[], int le, int ri){
	if (le >= ri) return;
	int mid = (le+ri)>>1;
	merge_sort(a, le, mid);
	merge_sort(a, mid+1, ri);
	
	int cnt=0, i=le, j=mid+1;
	while (i<=mid && j<=ri){
		if (a[i] <= a[j]) tmp[++cnt] = a[i++];
		else tmp[++cnt] = a[j++];
	}
	while (i<=mid) tmp[++cnt] = a[i++];
	while (j<=ri) tmp[++cnt] = a[j++];
	
	for (int i=1;i<=cnt;++i){
		a[i+le-1] = tmp[i];
	}
}

int main(void){
	n = read();
	for (int i=1;i<=n;++i){
		a[i] = read();
	}
	merge_sort(a, 1, n);
	for (int i=1;i<=n;++i){
		printf(i==n?"%d\n":"%d ", a[i]);
	}
	
	return 0;
}

快速排序

#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
1. 找到分界点x，q[L],q[(L+R)/2], q[R] 
2. 左边所有数Left<=x, 右边所有数Right>=x
3. 递归排序Left,Right

时间复杂度: O(NlogN)
 
*/
int n;
const int Max_n = 1e6 + 10;
int a[Max_n];

void quick_sort(int a[], int le, int ri){
	if (le >= ri) return;
	int i = le-1, j = ri+1, x = a[(le+ri)>>1];
	while (i < j){
		do i++; while (a[i] < x);
		do j--; while (a[j] > x);
		if (i < j){
			swap(a[i], a[j]);
		}
	}
	quick_sort(a, le, j);
	quick_sort(a, j+1, ri);
}

int main(void){
	n = read();
	for (int i=1;i<=n;++i){
		a[i] = read();
	}
	quick_sort(a, 1, n);
	for (int i=1;i<=n;++i){
		printf(i==n?"%d\n":"%d ", a[i]);
	}
	
	return 0;
}

快速选择（基于快排）

#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
在快排基础上，选取第k个数
假设对于分界点x，<=x的有sl个，>=x的有sr个 
1. k<= sl, 递归left
2. k> sl, 递归right, k-=sl
由于我们每次只选择两个区间中的一个，时间复杂度O(N) 
*/

int n, k;
const int Max_n = 1e6 + 10;
int a[Max_n];

int quick_sort(int le, int ri, int k){
	if (le == ri) return a[le];
	int x = a[le], i = le-1, j = ri+1;
	while (i < j){
		while (a[++i] < x);
		while (a[--j] > x);
		if (i < j){
			swap(a[i], a[j]);
		}
	}
	int sle = j-le+1;
	if (k <= sle){
		return quick_sort(le, j, k);
	}
	return quick_sort(j+1, ri, k-sle);
}

int main(void){
	n = read(), k = read();
	for (int i=1;i<=n;++i){
		a[i] = read();
	}
	int ans = quick_sort(1, n, k);
	printf("%d\n", ans);
}

/*
如果第26行 改成 x = a[(le+ri)>>2];对于数据
5 3
2 4 1 5 3
会陷入死循环，注意边界判断 
*/

求逆序对（基于归并排序）

#include <iostream>
using namespace std;
#define ll long long

int n;
const int Max_n = 1e6 + 10;
int a[Max_n], tmp[Max_n];

ll merge_sort(int a[], int le, int ri){
	if (le >= ri) return 0;
	int mid = (le+ri)>>1;
	ll res = merge_sort(a, le, mid) + merge_sort(a, mid+1, ri);
	
	int cnt = 0, i = le, j = mid + 1;
	while (i<=mid && j<=ri){
		if (a[i] <= a[j]) tmp[++cnt] = a[i++];
		else{
			tmp[++cnt] = a[j++];
			res += (mid - i + 1);
            // 主要思想就是j如果排在i前，那么i~mid这一段都会有个逆序数的贡献
		}
	}
	while (i <= mid) tmp[++cnt] = a[i++];
	while (j <= ri) tmp[++cnt] = a[j++];
	for (int i=1;i<=cnt;++i){
		a[i+le-1] = tmp[i];
	}
	return res;
}

int main(void){
	n = read();
	for (int i=1;i<=n;++i){
		a[i] = read();
	}
	ll res = merge_sort(a, 1, n);
	printf("%lld\n", res);
	
	return 0;
}

博弈论

公平组合游戏ICG

• 定义：若一个游戏满足

  • 由两名玩家交替行动
  • 在游戏进程的任意时刻，可以执行的合法行动与轮到哪位玩家无关
  • 不能行动的玩家判负

  则称该游戏为一个公平组合游戏。Nim博弈就属于公平组合游戏。

有向图游戏

• 给定一个有向无环图，图中有一个唯一的起点，在起点上有一枚棋子，两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动1步，无法移动者判负。这种游戏称为有向图游戏。

• 任何一个ICG都可以转化为有向图游戏。具体方法为，把每一个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Nim游戏

• 定义：给定N堆物品，第$i$堆物品有$a_i$个，两名玩家轮流行动，每次可以任选一堆，取走任意个物品。可以一次性把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否获胜。

• 定理：Nim博弈先手必胜，当且仅当$A_1 \oplus A_2...A_n \neq 0$。

如果不等于0，我们一定可以把它变为$A_1 \oplus A_2...A_n=0$，直至$A_1 = A_2...=A_n=0$，即拿光，对手无法再操作。证明：

假设$a_1\oplus a_2...a_n=x\neq 0$，$x$的二进制表示中最高位的1在第$k$位，则必然至少存在一个$a_i$，$a_i$的第$k$位二进制位为1，且$a_i\oplus x < a_i$。从$a_i$中拿走$a_i-(a_i\oplus x)$这么多石子，也就相当于把$a_i$变成$a_i \oplus x$。那么，剩下的所有石子的异或就变成了$a_1\oplus a_2.\oplus a_i \oplus x \oplus..a_n=x\oplus x = 0$。结论成立。

SG函数

• Mex运算：设S表示一个非负数整数集合，定义mex(S)为求出不属于集合S的最小非负整数的运算。

• 在有向图游戏中，对于每个结点$x$，设从$x$出发共有$k$条有向边，分别到达结点$y_1,y_2,...,y_k$，定义SG(x)的后继结点$y_1,y_2,...,y_k$的SG函数值构成的集合再执行mex(S)运算的结果，即：

$SG(x)=mex(SG(y_1), SG(y_2),...,SG(y_k))$

SG(终点)=0，SG(x)=x一步不能到达的最小非负整数。

特别的，整个有向图游戏G的SG函数值被定义为有向图起点$s$的SG函数值，即$SG(G)=SG(s)$

• 若只有一个游戏，先手面对$x$，$SG(x)=0$，必输；$SG=(x)\neq 0$，必赢。

例题：AcWing893

int n, m;
const int Max_n = 10000 + 10;
int op[Max_n], num[Max_n], f[Max_n];

int sg(int x){
	if (f[x] != -1) return f[x];
	unordered_set<int> us;
	for (int i=1;i<=m;++i){
		if (x >= op[i]) us.insert(sg(x-op[i]));
	}
	for (int i=0;;++i){
		if (us.count(i)==0){
			return f[x] = i;
		}
	}
	return -1;
}

void solve(){
	m = read();
	for (int i=1;i<=m;++i){
		op[i] = read();
	}
	n = read();
	for (int i=1;i<=n;++i){
		num[i] = read();
	}
	memset(f,-1,sizeof(f));
	f[0] = 0;
	int res = 0;
	for (int i=1;i<=n;++i){
		int x = num[i];
		res = res ^ sg(x);
	}
	if (res!=0) puts("Yes");
	else puts("No");
}

有向图游戏的和

设$G_1,G_2,...,G_m$是$m$个有向图游戏，定义有向图游戏$G$，它的行动规则是任选某个有向图$G_i$，并在$G_i$上行动一步，$G$被称为有向图游戏$G_1,G_2,...,G_m$的并（和）。

有向图游戏的和的SG函数等于它包含的各个子游戏SG函数值的异或和，即

$SG(G)=SG(G_1)\oplus SG(G_2)\oplus ...\oplus SG(G_m)$

证明方法和Nim游戏证明相同。

定理：

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

位运算小知识

概率与数学期望

公式1： $E(aX+bY)=a\times E(X)+b\times E(Y)$

奇奇怪怪小技巧

1. 拆数

$888..888=8\times 111..111=8\times \frac{999..999}{9}=8\times \frac{10^x-1}{9}$

$2334..899=111..111+1111+1111+...$

刷题

组合数 1622D Shuffle

给定一个01串$s[n]$，最多可以进行一次如下操作：选择一个包含精确的$k$个1的连续子串，然后将里面的元素任意排列。计算$s$最多可以获得多少种01串，答案模998244353。

数据范围：$2\leq n\leq 5000;0\leq k\leq n$。

嗯……首先，要不重不漏的枚举所有的方案，那么就可以枚举所有的$i,j$：在操作中第一个被改变和最后一个被改变的字符下标。然后判断它们是否可以属于同一个连续子串，如果可以的话，令c为$(i,j)$区间的长度，$c1$为$[i,j]$间中能自由移动的1的个数，那么改变$[i,j]$区间，其他部分保持不变的方案数就是$C(c,c1)$。这样的区间是不会有重复的，而且一旦改变了一个下标的位置的值，那就说明肯定还有另外一个下标被改变了，这样就保证了不重不漏啦。代码：

int n, m;
const int N = 5000 + 5, M = 998244353;
int C[N][N], f[N], pre[N];
char s[N];

void init(){
	for (int i=0;i<N;++i){
		for (int j=0;j<=i;++j){
			if (!j) C[i][j] = 1;
			else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % M;
		}
	}
	for (int i=1;i<=n;++i) pre[i] = pre[i-1] + (s[i]=='1');
}

int main(void){
	scanf("%d%d", &n, &m);
	scanf("%s", s+1);
	init();
	
	if (m == 0 || pre[n] < m){
		puts("1"); return 0;
	}
	
	ll ans = 1LL % M;
	for (int i=1;i<=n;++i){
		for (int j=i+1;j<=n;++j){
			int c = j - i + 1 - 2, c1 = pre[j] - pre[i - 1];
			if (c1 > m) continue;
			if (s[i] == '0') --c1;
			if (s[j] == '0') --c1;
			if (c>=c1 && c>=0 && c1>=0){
				ans = (ans + C[c][c1]) % M;
			}
		}
	}
	printf("%lld\n", ans);
	
	return 0;
}

暴力枚举贡献1622E Math Test

这题就要想到，绝对值只有两种形式，一种是$x_i-r_i$，一种是$r_i-x_i$，看到$n\leq 10$，因此直接枚举正负号情况，然后寻找其中的最大值就好啦。

那么这个surprise value就可以写成$\sum\limits _{i=1}^n |x_i-r_i|=\sum\limits _{i=1}^n c\times (x_i-r_i),c\in\{-1,1\}$。$x_i$是已知的，因此很容易就可以根据枚举的情况算出$\sum\limits _{i=1}^nc\times x_i$。那么怎么算学生的真实得分呢？首先啊，$p[m]$是一个排列，也就是每个问题都有一个1~m的权重，显然，如果我们要让$\sum\limits _{j=1}^np_jv_j$尽可能大，假设第$j$个问题对惊奇值的贡献系数是$v_j$，那就要让更大的贡献系数搭配更大的问题权重。因此，就对问题按照贡献系数的大小进行排序，就能算出结果啦。

int n, m;
const int N = 10 + 3, M = 1e4 + 5;
int g[N], p[M], a[M], best[M];
char s[N][M];
 
bool cmp(int x, int y){
	return a[x] < a[y];
}
 
void solve(){
	cin >> n >> m;
	for (int i=1;i<=n;++i) cin >> g[i];
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			cin >> s[i][j];
		}
	}
	for (int i=1;i<=m;++i) p[i] = i;
	
	int res = -1;
	for (int x=0;x<(1<<n);++x){
		for (int i=0;i<=m;++i) a[i] = 0;
		int half = 0;
		for (int i=1;i<=n;++i){
			int c = (((x>>(i-1))&1)?(1):(-1));
			half -= c * g[i];
			
			for (int j=1;j<=m;++j){
				if (s[i][j] == '1'){
					a[j] += c;
				}
			}
		}
		sort(p+1, p+1+m, cmp);
		int cur = half;
		for (int i=1;i<=m;++i){
			cur += a[p[i]] * i;
		}
		if (cur > res){
			res = cur;
			for (int i=1;i<=m;++i) best[p[i]] = i;
		}
	}
	
	for (int i=1;i<=m;++i){
		cout << best[i] << (i==m?"\n":" ");
	}
}

博弈论1537D Deleting Divisors

Alice和Bob又双叒在玩游戏，对于一个数字n，他们不断减去n的除了1和n之外的因子数，生成新的n。第一个无法进行操作的人就输了，Alice先手，问谁会赢。

$case1:$ 如果n为奇数，那么它肯定没有偶数因子，Alice必定只能减掉一个奇数因子$D$，减掉之后n就变成了一个偶数。并且，由于$(n-D)\%D=0$，所以$n-D \neq 2^k$。

$case2:$ 如果n为偶数并且$n \neq 2^k$，那么就可以分解成$n=D_{odd}*D_{even}$，那么就可以减去这个奇数因子$D$，偶数减奇数为奇数$n-D$。这样做一定是最优的：因为，如果$n-D$是质数，那么对手直接输了。如果不是，那么对手只能给我们一个新的$n$，使得$n \neq 2^k$，我们又可以进行重复操作，直到对手拿到质数输掉比赛。为什么新的$n \neq 2^k$呢？因为假如$n$可以被分解成$n=3*D$的形式，那么$3$的影响一直不会消失，直到$D=0$，此时$n=0$。

因此，如果$n=odd$，Bob赢，如果$n=even~And~n \leq 2^k$，Alice赢。

$case3:$ 如果$n=2^k$，那么只可能产生两种情况：1) 把n减半，此时$n=2^{k-1}$，要么，把$n$变成一个不是2的幂的偶数。如果丢给对手$n\%2=0~And~n=2^k$，在$case2$中我们可以发现自己就必输，所以双方只能不停的把$n$减半，直到有一方不能再减，那一方就输了。

因此，如果$n=2^k$，如果$k=odd$，Bob赢，否则，Alice赢。

组合数+思维 1569C Jury Meeting

首先把$a[n]$数组排序，如果最大值$a_n$的数量$>1$，那么所有排列都是$nice$。

下面讨论$a[n]$的数量为1时的情况。$nice$的排列数量$=$能构成的排列数量$-$坏的排列的数量。在坏的排列中，所有的小于$a[n]-1$的元素都要排在$\geq a[n]-1$的元素之前。也就是$A^{n-k-1}_n=\frac{n!}{(k+1)!}$。设等于$a[n]-1$的元素数量为$k$，保证$a[n]$在最后一个位置，剩下$k$个数有$k!$种排列方式，因此坏的排列的数量为$\frac{n!k!}{(k+1)!}=\frac{n!}{k+1}$。

$nice$的排列数量$=n!-\frac{n!}{k+1}$。

AC代码：

int n;
const int Max_n = 2e5 + 10;
const ll MOD = 998244353;
ll a[Max_n];
 
void solve(){
	n = read();
	ll maxa = 0;
	for (int i=1;i<=n;++i){
		a[i] = read();
		if (a[i] > maxa) maxa = a[i];
	}
	sort(a+1, a+1+n);
	ll num = count(a+1, a+1+n, a[n]-1) + 1;
	ll sub = 1, ans = 1;
	for (ll i=1;i<=n;++i){
		ans = ans * i % MOD;
		if (i != num) sub = sub * i % MOD;
	}
//	cout << "!!" << num << endl;
	if (count(a+1,a+1+n, maxa) > 1){
		printf("%lld\n", ans);
		return;
	}
	ans = (ans - sub + MOD) % MOD;
	printf("%lld\n", ans);
} 

DP 1581C Portal

给定一个矩阵，每次操作可以将矩阵中的0变为1，或者将1变为0，求将矩阵的连续子矩阵变为如下形式（最少5行4列）需要的最小操作数：

上下左右都是1，中间都是0，四个角上的元素任意。很容易想到用二维前缀和，然后枚举。嗯……但是没想到怎么枚举，才能把复杂度降到$O(n^2m)$。

这题是这样的，枚举子矩阵的第一行，最后一行的位置，然后枚举子矩阵第一列的位置，从最后的可能开始枚举，然后更新右半边，看右半边是加之前的结果比较好，还是直接加最后新的一列比较好，也就是一种利用前面计算结果的一种方式，把复杂度从$O(n^2m^2)$降到$O(n^2m)$的一种方式。我记得有一题也是差不多，翻转数组子序列的左右，用半径来简化的，这种都是巧妙利用之前结论的方式（不知道这种应该叫啥）

b，mina如图所示

AC代码如下：

int n, m;
const int Max_n = 400 + 10;
const int INF = 1e9 + 10;
int pre[Max_n][Max_n], a[Max_n][Max_n];

// 求这块矩形之和
int rect(int a1, int b1, int a2, int b2){
	return pre[a2][b2] - pre[a1-1][b2] - pre[a2][b1-1] + pre[a1-1][b1-1];
}

void solve(){
	cin >> n >> m;
	char ch;
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			cin >> ch;
			a[i][j] = ch - '0';
			pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
		}
	} 
	int ans = INF;
	for (int i=1;i<=n;++i){
		for (int j=i+4;j<=n;++j){
			int mina = INF, h = j-i+1;
			for (int x=m-3;x>=1;--x){
				// b就是左边的一部分 
				int b1 = h - 2 - rect(i+1, x, j-1, x);
				int b2 = 2 - rect(i, x+1, i, x+2);
				int b3 = 2 - rect(j, x+1, j, x+2);
				int b4 = rect(i+1, x+1, j-1, x+2);
				int b = b1 + b2 + b3 + b4;
				// 将上次的最好的mina加上新的增加的中间的部分，和只要新的最后一列的答案比较，更新右边那部分答案 
				mina = min(mina + !a[i][x+3] + !a[j][x+3] + rect(i+1, x+3, j-1, x+3), h - 2 - rect(i+1, x+3, j-1, x+3));
				// 更新答案 
				ans = min(ans, b+mina);
			}
		}
	}
	printf("%d\n", ans);
}

思维+统计贡献 1526D Kill Anton

https://codeforces.com/contest/1526/problem/D

一个字符串$s$仅由ANOT四个字符构成，要求构造出一个$s$的排列$t$，使得$t$​​经过最多的操作次数，才能变回$s$​。对一次操作的定义为：交换任意相邻的两个字符$s_i$和$s_{i+1}$​​。

我自己的思路：

首先，我们可以想到，最终的答案，相同的字符应该是连在一起出现的。因为如果是分开的话，可能会变成这样：

本来是想把开头的A调换到最后一位的，但是由于采取最优策略，把离N最近的A调换到了最后面。除非变成这样，使得所有的A调换到后面都要花费很多距离，也就是所有的A都挨在一起。当然这只是我做题时候感性的想法。那么一共只有4个字符，只要把所有排列情况全部算一遍，看他们谁需要调换的次数最多，就输出那种排列方式。

有了这个想法之后，我发现自己不知道怎么算调换次数QAQ。然后看了dalao的算法。

for (int i=0;i<4;++i){
    for (int j=0;j<4;++j){
        if (i==j) continue;
        int num = 0;
        for (int k=0;k<slen;++k){
            if (a[k]==i) score[i][j]+=num;
            if (a[k]==j) num++;
        }
    }
}

程序结束之后，$score[i][j]$中存储的就是每个$i$类型的字符，前面有多少个$j$类型的字符。那么，很显然，如果要把所有$i$类型字符调换到最前面，那么花费的操作次数就是$\sum\limits_{j=0}^4score[i][j]$。然后，如果$k$类型字符，要调换到$i$的后面，那么花费的操作次数就是$\sum\limits_{j=0}^4score[k][j]-score[k][i]$。以此类推，当确定了字符串的排列$p$后，则可以算出当前排列需要花费的操作次数$now$，$now=\sum\limits_{i=0}^4\sum\limits_{j=i+1}^4score[p_i][p_j]$​。好巧妙！真的写的很巧妙很漂亮啊！

完整的AC代码在这里啦：

{% raw %}
string s;
string ex="ANOT";
map<char,int> ma = {{'A',0},{'N',1},{'O',2},{'T',3}};
const int Max_n = 1e5 + 10;
int a[Max_n];
ll cnt[4], score[4][4];

void init(){
	memset(cnt,0,sizeof(cnt));
	memset(score,0,sizeof(score));
}

void solve(){
	cin >> s;
	int slen = s.size();
	init();
	for (int i=0;i<slen;++i){
		a[i] = ma[s[i]];
		cnt[a[i]]++;
	}
	for (int i=0;i<4;++i){
		for (int j=0;j<4;++j){
			if (i==j) continue;
			int num = 0;
			for (int k=0;k<slen;++k){
				if (a[k]==i) score[i][j]+=num;
				if (a[k]==j) num++;
			}
		}
	}
	ll res = -1;
	vector<int> best;
	vector<int> p = {0,1,2,3};
	do{
		ll now = 0;
		for (int i=0;i<4;++i){
			for (int j=i+1;j<4;++j){
				now += score[p[i]][p[j]];
			}
		}
		if (now > res){
			res = now;
			best = p;
		}
	}while (next_permutation(p.begin(), p.end()));
	string ans;
	for (int i=0;i<4;++i){
		for (int j=0;j<cnt[best[i]];++j){
			ans += ex[best[i]];
		}
	}
	cout << ans << endl;
}
{% endraw %}