基本上只是整理了一下框架QAQ
PART1 数论部分
最大公约数
对于正整数x,y,最大的能同时整除它们的数称为最大公约数
常用的：\(lcm(x,y)=xy\gcd(x,y)\)
裴蜀定理
定理：对于方程\(ax+by=c\)，其存在解的充要条件是\(gcd(a,b)|c\)，可以拓展到n元的方程。
证明的话应该自己yy一下还是很容易（显然可得），不过要是想要严谨证明还是去百度吧qwq
扩展欧几里得定理
首先我们都知道\(gcd(a,b)=gcd(b,a \%b)\)吧。
我们在辗转相除的同时可以递归地求出\(ax+by=gcd(a,b)\)的解。当递归到b=0的时候，显然有解\(x=1,y=0\)。如果b!=0，我们可以递归的求出\(bx'+(a\%b)y'=gcd(a,b)\)的解。
\[bx'+(a\%b)y'=bx'+(a-\lfloor \frac{a}{b}\rfloor\times b)y'=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')
\]
所以\(x=y',y=(x'- \lfloor \frac{a}{b} \rfloor y')\)
时间复杂度：O(log n)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,p;
inline void exgcd(int a,int b,int &x,int &y)
{
if(b==0) {x=1,y=0;return;}
else
{
int tx,ty;
exgcd(b,a%b,tx,ty);
x=ty;
y=tx-(a/b)*ty;
return;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
int x,y;
exgcd(i,p,x,y);
while(x<0) x+=p;
printf("%d\n",x);
}
return 0;
}
逆元
定义：
若有\(xy=1\pmod p\)，则称y为x模p意义下的乘法逆元
计算方法：
转换为方程：\(xy-kp=1\)，用拓展欧几里得算法就可以了。当然费马小定理也可以，只不过时间复杂度上稍微逊色一些。（还有一种线性的，不过我不会）
补充：费马小定理：若p为质数，对于任意\(1<=a<p,a^{p-1}\equiv 1 \pmod p\),那么在p为质数的时候\(a^{p-2}就是a的逆元\)
对于费马小定理的补充：\(a^b\equiv a^{b\%(p-1)}\pmod p\)
欧拉筛（线性筛）
在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
模板：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define MAXN 10000010
using namespace std;
int cnt,n,m;
int not_prime[MAXN],prime[MAXN];
inline void init(){
not_prime[1]=1;
for(int i=2;i<=MAXN;i++){
if(not_prime[i]==0){
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=MAXN-10;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&m,&n);
init();
while(n--){
int a;
scanf("%d",&a);
if(not_prime[a]==0) printf("Yes\n");
else printf("No\n");
}
return 0;
}
不过有一组性质，下面会提到（在约数个数和那里）
积性函数
对于任意互质整数a,b，存在\(f(ab)=f(a)f(b)\)性质的数论函数。
（积性函数的卷积仍然是积性函数）
完全积性函数则是没有互质的限制。
常见的积性函数举例：
φ(n) －欧拉函数
μ(n) －莫比乌斯函数，关于非平方数的质因子数目 \(μ(n)=[k_1\le1][k_2\le1]...[k_m\le1](-1)^m\)
gcd(n,k) －最大公因子，当k固定的情况
d(n) －n的正因子数目
\(σ_k(n)\) －n的所有正因子的k次方之和（0次方的时候就是所有因子和了）\(σ_k(n)=n*\frac{p1-1}{p1}...\frac{p_m-1}{p_m}\)
积性函数都可以用线性筛筛出来
欧拉函数
定义：\(\phi(n)\)定义为1-n内与n互质的数的个数
\(\phi(x)=x\prod_1^n(1- \frac{1}{p_i})\)，其中x是正整数，\(p_i\)是x的质因数。
这个的计算程序十分好写。
特别的，欧拉函数是积性函数，即 \(\phi(mn)=\phi(m)\phi(n)\)。
证明比较显然。
这个样子是可以用线性筛，用线性的时间复杂度筛出来欧拉函数的答案——
那么φ(1)=1，n为质数时φ(n)=n−1，最小质因子筛到它时乘上质因子p−1，否则乘上这个质数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 110
using namespace std;
int cnt;
int not_prime[MAXN],phi[MAXN],prime[MAXN];
inline void solve()
{
for(int i=2;i<MAXN;i++)
{
if(!not_prime[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<MAXN;j++)
{
not_prime[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main()
{
solve();
for(int i=1;i<=36;i++) printf("phi[%d]=%d\n",i,phi[i]);
return 0;
}
线性求逆元
在模p意义下求i的逆元：
\(p=i*x+y\)
那么\(i*x+y\equiv0\pmod p\)
两边除以\(ij\)
\(x*j^{-1}+i^{-1}\equiv0\pmod p\)
\(i^{-1}\equiv-x*j^{-1}\pmod p\)
\[i^{-1}\equiv-\lfloor\frac{p}{i}\rfloor*(p\%i)\pmod p
\]
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
阶乘逆元的递推
其实把最后的那个\(inv[i]\)求出来，然后逆着一路乘上来就行了。
约数个数的递推
学习来源
理论基础：
1、对n质因数分解，\(n=p1^k1 * p2^k2 * p3^k3\) ……
则n的约数个数为\((k1+1)*(k2+1)*(k3+1)\)……
2、线性筛素数时，用i和素数pj来筛掉 i*pj，
其中pj一定是i*pj的最小素因子
如果i是pj的倍数，pj也是i的最小素因子
设\(t[i]\) 表示i的约数个数，\(e[i]\) 表示i的最小素因子的个数
A、如果i是质数，\(t[i]=2,e[i]=1\)
B、如果i不是质数，枚举已有的质数\(p_j\)
i*pj的最小素因子是pj
1、如果i是pj的倍数那么e[i]即为i中包含的pj的个数，所以i*pj中包含的pj的个数为\(e[i]+1\)
所以\(e[i*pj]=e[i]+1,t[i*pj]=t[i]/(e[i]+1)*(e[i]+2)\)
2、如果i不是pj的倍数
\(e[i*pj]=1,t[i*pj]=t[i]*t[pj]\)（积性函数的性质）
\(=t[i]*2\)（素数的约数个数=2）
inline void init()
{
memset(is_prime,1,sizeof(is_prime));
is_prime[1]=0,mu[1]=1,d[1]=1;
for(int i=2;i<=limit;i++)
{
if(is_prime[i]) prime[++cnt]=i,e[i]=1,d[i]=2,mu[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<=limit;j++)
{
is_prime[i*prime[j]]=0;
e[i*prime[j]]=1;
if(i%prime[j]==0)
{
e[i*prime[j]]+=e[i];
mu[i*prime[j]]=0;
d[i*prime[j]]=d[i]*(e[i*prime[j]]+1)/e[i*prime[j]];
break;
}
mu[i*prime[j]]=-mu[i];
d[i*prime[j]]=d[i]*2;
}
}
}
线性筛约数和
\(t[i]\) 表示i的约数和
\(e[i]\) 表示i的约数中，不能被i的最小素因子整除的约数和
A、i是质数，\(t[i]=i+1,e[i]=1\)
B、i不是质数
\(i*pj\)的最小素因子是\(pj\)
1、如果i不是pj的倍数，那么i的所有约数中，必然没有pj的倍数
可以用反证法证明这个：设x是i的约数，且x是pj的倍数，
那么\(x=pj*b,i=x*a=pj*b*a\)
即i是pj的b*a倍，与i不是pj的倍数相矛盾
令S表示i的约数集，S’表示i的约数翻pj倍后的数的集合
则S∩S’=∅，则S和S’中无重复元素
所以\(t[i*pj]=S+S'=t[i]+t[i]*pj=t[i]*(pj+1)\)
S’中的所有元素都能整除pj，所以\(e[i*pj]=t[i]\)
2、如果i是pj的倍数，那么S和S’必有交集T
T=S中pj的倍数
所以\(i*pj\)的约数和要去除交集T
那么\(t[i*pj]=S+S'-T=S'+S-T=t[i]*pj+e[i]\)
因为pj既是i的最小素因子，又是\(i*pj\)的最小素因子
所以\(e[i*pj]=e[i]\)
isprime[1]=1;
for(int i=2;i<=n;i++)
{
if(!isprime[i])
{
prime[++num]=i;
t[i]=i+1;
e[i]=1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
isprime[i*prime[j]]=1;
if(i%prime[j]==0)
{
t[i*prime[j]]=t[i]*prime[j]+e[i];
e[i*prime[j]]=e[i];
break;
}
else
{
t[i*prime[j]]=t[i]*(prime[j]+1);
e[i*prime[j]]=t[i];
}
}
}
欧拉定理&扩展欧拉定理
欧拉定理——需要\(a,m\)互质：$$a^{\phi(m)}\equiv1\pmod m$$
拓展欧拉定理——
\[a^b\equiv\begin{cases}a^{b\%\phi(p)}&{gcd(a,p)=1}\\a^b&{gcd(a,p)=1,b\le\phi(p)}\\a^{b\%\phi(p)+\phi(p)}&gcd(a,p)\neq1,b\ge\phi(p)\end{cases}\pmod p
\]
证明请看这篇博客 戳我
Miller-Rabin素性测试
因为当p为质数且\(1<=a<p\)时，\(a^{p-1}\equiv 1\pmod p\)（欧拉定理）
那么当\(1\le a<p\)且\(a^{p-1}\equiv 1\pmod p\)时，p是否一定是质数呢？
当然不是啦！但是我们发现大部分合数都不满足这个性质。
所以我们的素数判定算法出世啦！随机几个a，判断\(a^{p-1}\mod p\)是否为1——不过这个正确性有点玄学，因为有些合数对任意的a的也都满足这个性质emmmmm，所以需要对算法进行改进。
这样就引出了我们的二次探测定理——
在进行Miller-rabbin算法之前，先筛去偶数，接下来只需要对奇数进行判断。
于素数p而言，任意x=1,...,p-1，都有\(x^p\equiv x\pmod p\)，而于合数，这个等式不一定成立。根据这个性质，如果找到了\(1\le x<n\)且不满足\(x^n\equiv x\pmod n\),说明这个数n一定是合数。
然而存在一些Carmichael数（比如说561），虽然是合数，但x取遍1,...,n-1都满足\(x^n\equiv \pmod n\)
考虑\(x^2\equiv 1\pmod n\)的根，如果n是奇素数，只有1和n-1两根：若n是奇合数，一定存在其他的根。
设\(n-1=2^r*d\),其中d是奇数。若存在\(0\le k<r\),\(a^{2^k*d}\)不同余1或-1(mod n),但是\(a^{2^{k+1}*d}\equiv1 \pmod n\)，可推断n一定是合数。
算法时间复杂度是log的。
加上这个玄学改进，如果我们随机的a够多，几乎就卡不掉了。随机k个判断错误的概率仅有\(\frac{1}{2^k}\)。
对于int32范围内的数，使用2，7，61探测即可。对于int64范围内的数，使用前10个素数作为探测基底即可保证算法成功。
Pollard-Rho大整数质因数分解算法
听说没有什么大用qwq？？？蒟蒻选择战略性放弃
中国剩余定理(CRT)
void exgcd(int a,int b,int &x,int &y)
{
if(b==0){ x=1; y=0; return;}
exgcd(b,a%b,x,y);
int tp=x;
x=y; y=tp-a/b*y;
}
int china()
{
int ans=0,lcm=1,x,y;
for(int i=1;i<=k;++i) lcm*=b[i];
for(int i=1;i<=k;++i)
{
int tp=lcm/b[i];
exgcd(tp,b[i],x,y);
x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解
ans=(ans+tp*x*a[i])%lcm;
}
return (ans+lcm)%lcm;
}
exCRT
咕咕
BSGS
bsgs就是哈希表(或map)+分块结合起来的优美算法。
一般用来解决求\(a^x\equiv y\pmod p\)有解的（最小）x。
一般我们令\(x=i*m-j\)，（如果向别人那样写\(x=i*m+j\)到最后是需要exgcd的）。其中\(m=\sqrt p\)（因为这样时间复杂度最优，总体时间复杂度即\(O(\sqrt p)\)）
然后有\(a^{im-j}\equiv y\pmod p\)
\(a^{im}\equiv y*a^j\pmod p\)
之后我们枚举j（\(j\in[0,m-1]\)）,把右边的值塞进哈希表里面（或者map也行）。
for(int i=0,t=z;i<m;t=1ll*t*y%p,i++) M[t]=i;
最后枚举i看看哈希表里有没有原先已经塞进去的值了。如果有，就输出\(im-j\)即可。
for(int i=1,tt=pow(y,m),t=tt;i<m;i++,t=1ll*tt*t%p)
if(M.count(t)) {printf("%d\n",m*i-M[t]);flag=true;break;}
一定要注意中间乘起来的时候加上*1ll！！！
拓展BSGS
咕咕
斐波那契数列循环节
咕咕
二次剩余
PART2 组合数学部分
求组合数的几种方法
公式法 （这个复杂度很劣）
阶乘逆元求法 适用于多次查询，复杂度预处理O( n+logn )，查询接近O( 1 )，但是模数必须是质数。（100007不是质数）
（就是先O(n)预处理阶乘，然后算出来最大数的逆元，然后倒推回来。）
杨辉三角递推求法 适用于多次密集小范围查询，复杂度预处理O( n^2 )，查询O( 1 )
费马小定理/exgcd求逆元 单次O( logn )，是最简单的方法，模数必须为质数
阶乘分解 适用于模数不为质数的求法。复杂度预处理O( nlogn )，查询O( 1 )
Lucas定理（适用于处理long long级别大整数，但是模数不是很大（一般都是1e5级别）的情况）
lucas定理
\(lucas(n,m,p)=c(n\%p,m\%p)\times lucas(n/p,m/p,p)\)，其中p是模数。
\(O(p)\)预处理之后,一次计算时间复杂度上界\(O(lognlogp)\)。
排列组合
这个蒟蒻我原先有过整理了，算是写了很多吧。戳我
不过那个是在NOIP前搞的了，所以现在看来又显得简单了一些。
所以现在特地来补充一下。
卡特兰数
以下内容摘抄自：这里
卡特兰数的公式
通项公式1：\(C_n=\frac{1}{n+1}C_{2n}^n=C_{2n}^n-C_{2n}^{n-1}\)
通项公式2：\(C_n=\frac{1}{n+1}\sum_{i=0}^n(C_n^i)^2\)
递推公式1：\(C_{n+1}=\frac{2(2n+1)}{n+2}C_n,\)且\(C_0=1\)
递推公式2：\(C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i-1},\)且\(C_0\)=1
卡特兰数的应用
进出栈问题
对于一个足够大的进栈顺序为1,2,3...,n时有多少个不同的出栈序列？
二叉树构成问题
有n个节点，问总共能构成多少种不同的二叉树。
我们可以假设，如果采用中序遍历的话，根节点第K个被访问到，则根节点的左子树有K-1个点，根节点的右子树有N-K个点，K的取值范围为1到N。
凸多边形的三角划分
一个凸的N边形，用直线连接他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分方案。
选择一个基边，显然这是多边形划分完之后某个三角形的一条边。图中我们假设基边是p1pn，我们就可以用p1、pn和另外一个点假设为pi做一个三角形，并将多边形分成三部分，除了中间的三角形之外，一边是i边形，另一边是n-i+1边形。i的取值范围是2到n-1。所以本题的解\(c(n)=c(2)*c(n-1)+c(3)*c(n-2)+...c(n-1)*c(2)\)。令\(t(i)=c(i+2)\)。则\(t(i)=t(0)*t(i-1)+t(1)*t(i-2)...+t(i-1)*t(0)\)。
在n*n的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？其实向右走相当于进栈，向左走相当于出栈，本质就是n个数出栈次序的问题。
有n+1个叶子的满二叉树的个数？事实上，向左记为+1，向右记为−1，按照向左优先的原则，从根节点开始遍历．例如第一个图记为+1,+1,+1,−1,−1,−1,于是由卡特兰数的含义可得满二叉树的个数为Cn。
由n对括号组成的合法括号表达式的种类数为\(C_n\)
n+1个数连乘，不同的乘法顺序为\(C_n\)种。
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？和凸包切割一个原理。
卡特兰数的前几项：1,2,5,14,42......
容斥
新开了一个，详情请看这个吧
PART3 线性代数部分
向量
n维向量可以看成n个数组成的n元组（或者说n个元素的数组）
几何意义：表示n维空间中的方向和长度
矩阵
行列式
一般用\(|A|\)或者\(det(A)\)表示A的行列式。
把一个n阶行列式中的元素\(a_{ij}\)所在的第i行和第j列划去后，留下来的n-1阶行列式叫做元素\(a_{ij}\)的余子式,记作\(M_{ij}\)。记\(A_{ij}=(-1)^{i+j}M_{ij}\)，叫做元素\(a_{ij}\)的代数余子式。
一个n×n矩阵的行列式等于其任意行(或列)的元素与对应的代数余子式乘积之和，即
\[det(A)=a_{i1}M_{i1}+...+a_{in}M_{in}
\]
以下内容参考了这篇来自candy? dalao博客
行列式的性质:
\(det(A)=det(A^T)\)
行列式的行和列是平等的，行满足那么列也满足。
令A为n×n矩阵。
若A有一行或一列包含的元素全为零，则det(A)=0。
若A有两行或两列相等，则det(A)=0。（因为两行互换，行列式变号）
一行乘上k,行列式乘上k
推论：行列式两行成比例或一行全0，值为0
两个行列式只有一行不同，他们的行列式和等于不同的行相加后的行列式
每行每列和均为0的矩阵行列式为0。
求法：用高斯消元的方法将其化成一个上三角矩阵，然后主对角线相乘就是行列式的值。
主子式
n−1阶主子式，就是对于r，第r行、第r列同时去掉后得到的新行列式
高斯消元
解线性方程组，在概率与期望的题中作为一种解题方法还是蛮常见的。
无解情况：化简后的有效方程组出现(0=d)型式不兼容方程，则无解 。（如下例）
\[\begin{bmatrix}
1& -7& 6& | 2 \\
0& 17& -20& |-1 \\
0& 0& 0& |5 \\
\end{bmatrix}
\]
无穷多解情况：化简后的有效方程组个数，小于未知数个数。这样的方程组有无穷多个解。（如下例）
\[\begin{bmatrix}
& \text{ } 2x_{1}+3x_{2}+x_{3}=2 \\
& \text{ }7x_{2}-3x_{3}=6 \\
& \text{ } 0x_{1}+0x_{2}+0x_{3}=0 \\
& \text{ } \\
\end{bmatrix}
\]
矩阵树定理
用来解决生成树计数问题：对于一张包含N个节点的无向图，求包含N-1条边且这些边集能够构成一棵树的种类数。
定理：G的所有不同的生成树的个数等于其基尔霍夫矩阵C[G]（度数矩阵-邻接矩阵）任何一个n−1阶主子式的行列式的绝对值。
证明：请看wzs dalao的博客 戳我
模板题：[HEOI2015]小Z的房间
计算几何
这个开成专题了，详情请参考同系列学习笔记->OI计算几何 简单学习笔记
PART4 我也不知道这是什么分类了
范德蒙矩阵
相关的主要就是求行列式。这个感觉百度百科上说的很详细了，也有证明，链接戳我。
点值表示
我们可以用n个不同的\(y_i=A(x_i)\)，用这n个点来表示一个次数界为n的多项式，称作多项式的点值表示。
利用点值进行多项式加法和乘法只需要把\(y_i\)的值乘或加起来即可，时间复杂度\(O(n)\)
我们想到可以把系数表示转化成点值表示（求值），做乘法再转化回来（插值），就能快速计算卷积。
点值对应唯一的多项式，证明是可以将它转化成矩阵来推，与范德蒙矩阵有关，具体证明可以看《算法导论》。
拉格朗日插值公式
\[A(x)=\sum_{i=0}^{n-1}y_i\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}
\]
欧拉公式：\(e^{ix}=cosx+isinx\)
第一类斯特林数
用n个数组成k个圆排列的方案数
\[dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*(i-1)
\]
第二类斯特林数
dp[n][m]表示n个有区别的小球，放进m个相同的盒子里，且每个盒子非空的方案数
\[dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j
\]
数论分块
求\(\sum i\times \lfloor \frac{k}{i}\rfloor\)
for(long long l=1,r;l<=n;l=r+1)
{
if(k/l!=0) r=min(n,k/(k/l));
else r=n;
ans+=(l+r)*(r-l+1)/2*(k/l);
}
莫比乌斯反演
其实是一种容斥。。。。
推荐pengym dalao的博客 戳我
二项式反演
其实是利用的容斥定理。以下是两种常见形式。
\[f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i
\]
\[f_n = \sum_{i=0}^n {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i
\]
杜教筛
套路式：
现在要求的式子为\(\sum_{i=1}^nf(i)\)
那么我们找到合适的\(h,g\)，使得\(h=g*f\)
那么根据狄利克雷卷积，我们有\(h(n)=\sum_{d|n}^{} g(d)f(\frac{n}{d})\)
\(\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{n}{d})\)
我们令\(s(n)=\sum_{i=1}^nf(i)\)，之后就可以进行推导了：
\(\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{n}{d})\)
\(\sum_{i=1}^nh(i)=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\)（这一步不理解的话可以自己找个例子试一试帮助理解）
\(\sum_{i=1}^nh(i)=\sum_{d=1}^ng(d)s(\lfloor\frac{n}{d}\rfloor)\)
\(\sum_{i=1}^nh(i)=g(1)s(n)+\sum_{d=2}^ng(d)s(\lfloor\frac{n}{d}\rfloor)\)
\(g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)s(\lfloor\frac{n}{d}\rfloor)\)
当h(i)的前缀和可以很快地求出来之后（比如说时间复杂度O（1）），当我们对后面的式子进行整除分块时，求S(n)的复杂度为\(O(n^{\frac{2}{3}})\)
更详细的请见pengym dalao的博客 戳我
补：yyb dalao还有几篇复习向的有关多项式的博客，写的挺好的orz
PART5 博弈论
Nim游戏
结论：将每堆石子的石子个数异或起来，如果得到的结果为0，先手必败，否则先手必胜。
证明：对于一个异或和为0的局面，由于我们进行一次操作必然会改变局面的异或和，必然不能到达异或和为0的局面。对于一个异或和不为0的局面，设现在的异或和为s，考虑异或和s二进制下最高位j，我们找到一堆石子ai，满足ai二进制下该位为1（因为异或和的性质，该堆石子必然存在），那么\(ai\) \(xor\) \(s<ai\),也就是说必然存在到达异或和为0的局面的操作。
于是我们发现异或和是否大于0与先手是否必胜等价。
游戏的和
若局面X由若干个子游戏X1,X2,...,Xn构成，则\(SG(x)=SG(X_1) xo rSG(X_2)xor...xorSG(X_n)\)
SG函数
若干个平等博弈游戏之和定义为两人轮流操作，每次操作选择一个游戏进行一次操作，不能操作者为负的平等博弈。
对于非负整数组成的集合S，我们定义mex(s)为最小的没有在s中出现的非负整数。
对于局面x，我们定义mex(s)为最小的没有在s中出现的非负整数。
显然，若SG(x)>0，先手必胜，若SG(x)=0，先手必败。
SG定理：平等博弈游戏和的SG函数等于各游戏SG函数的异或和。
证明：
我们只需要证明对于一个可拆分成若干个子游戏的平等博弈，若其子游戏SH异或和为x，其不能通过一次操作到达异或和为x的状态且能到达异或和为0~x-1内的每个状态。
首先，对于一个子游戏进行操作，必然会改变其SG函数的值，异或和也必然会改变，故不能到达异或和为x的状态。
之后再证能到达异或和为0~x-1内的每个状态，证明与Nim游戏异曲同工。
反Nim游戏
规定取走最后一块石子的人输（也就是轮到一个人不能操作的时候他赢）
结论：若每对石子都只有一个石头，石子数异或和为0时先手必胜，否则石子数异或和非0时先手必胜，其他情况先手必败。
证明：
如果每堆石子都只有一个石头，因为奇偶性，结论显然。
如果只有一堆大于1的石头（此时异或和一定非0），我们必然能将其变成1或者0而转到必败态。所以先手必胜。
若不止一堆，那么操作后至少会剩一堆。那么进行几轮之后，就相当于进入了上一种局面，所以是先手必败。
例题 [SHOI2008]小约翰的游戏john
反博弈
改变了一点，就是将不可操作定义为胜利。
结论：如果任意子游戏x都满足当SG(x)=0时，x不可操作或者x一定能转移到SG函数为1的状态，那么当以下两个条件同时满足或者同时不满足的时候，先手必胜。
1、所有子游戏的SG函数值异或和为0
2、所有子游戏的SG函数值小于等于1
PART6 概率与期望
全概率公式
把样本空间S分为若干个不相交的部分B1,B2,B3....,Bn，则\(P(A)=P(A|B_1)\times P(B_1)+P(A|B_2)\times P(B_2)+...+P(A|B_n)\times P(B_n)\)。
数学期望
随机变量X的数学期望EX就是所有可能值按照概率加权的和，在非正式场合中，数学期望可以被称作“在平均情况下”。
在解决数学期望相关的题目时，可以先考虑直接使用数学期望的定义求解，计算出所有可能取值，以及对应的概率，最后加权求和。以下还有两个比较常用的性质——
期望的线性性
有限个随机变量之和的数学期望等于每个随机变量的数学期望之和。
全期望公式
类似于全概率公式，把所有情况不重复、不遗漏地分成若干类，每类计算数学期望，然后把这些数学期望按照每类的概率加权求和。
PART7 群论
置换
（注：以下部分内容参考自蓝书）
置换是把n个元素做一个全排列。比如说一般把1变成\(a1\),2变成\(a2\)...的置换记作：
\[ \begin{pmatrix}
1 & 2 &... & n \\
a_1 & a_2 & ... & a_n \\
\end{pmatrix}
\]
置换可以定义乘法，对应于函数复合。有封闭性。满足结合律，但是不满足交换律。有单位元。有逆元。
为了处理方便，常常把置换分解成循环的乘积。而且对于任意置换，只有唯一的方法表示成不相交的循环的乘积比如说
\[\begin{pmatrix}
1&2&3&4&5\\
3&5&1&4&2\\
\end{pmatrix}
=(1\;3)(2\;5)(4)\]
为什么任意置换都可以这样分解？因为我们把每个元素看程一个节点，如果a变成b，连一条有向边\(a\to b\),则每个元素恰好有一个后继节点和一个前驱节点。（就是每个点的入度和出度都为1），那么这样的图只能是若干个有向环，其中每一个环都对应一个循环。
Burnside引理
对于一个置换f，若一个着色方案s经过置换后不变，那么称s为f的不动点。将f的不动点数目记为\(C(f)\),则可以证明等价类数目为所有的\(C(f)\)的平均值。（注意不动也是一种方案）
polya定理
（以下内容摘自beisong dalao的博客）
polay定理实际上是burnside引理的具体化，提供了计算不动点的具体方法。
假设一个置换有k个循环，易知每个循环对应的所有位置颜色需一致，而任意两个循环之间选什么颜色互不影响。因此，如果有m种可选颜色，则该置换对应的不动点个数为\(m^k\)。用其替换burnside引理中的C(f)，得到等价类数目为：
\[\frac{\sum_{i=0}^{|F|}m^{k_i}}{|F|}\]
其中|F|表示置换的数目，ki表示第i个置换包含的循环个数。
