GOOD BYE OI

雨点打透心脏的1/2处 2021-10-20 19:54 425阅读 0赞

**大米饼正式退役了，OI给我带来很多东西  
我会的数学知识基本都在下面了  
博客园的评论区问题如果我看到了应该是会尽力回答的．．．  
这也是我作为一个OIer最后一次讲课的讲稿  
20190731**

## 多项式乘法 ##

### FFT ###

**基本概念**

1.多项式的两种表达(拉格朗日插值法)

多项式：\$A(x) = \\sum\_\{i=0\}^\{n-1\}a\_ix^i\$，最高项次数为\$n-1\$，次数界为\$n\$

\$(a\_0,\\cdots,a\_\{n-1\})\$为多项式的系数表达, \$(x\_0,y\_0),\\cdots,(x\_\{n-1\},y\_\{n-1\})\$ 为多项式的点值表达

2.\$n\$次单位根(泰勒展开(对多项式也适用)，欧拉公式，单位根，引理)

泰勒展开：

函数f(x)在\$x=x\_0\$除的展开为：

$f(x) = f^0(x\_0) + f^1(x\_0)(x-x\_0) + f^2(x\_0)\\frac\{(x-x\_0)^2\}\{2!\} + \\cdots + f^i (x\_0)\\frac\{(x-x\_0)^i\}\{i!\} +\\cdots $

其中\$f^i(x)\$表示\$f(x)\$的\$i\$次导数(所以要运用首先你得记住初等函数的求导公式)：  
\\\[ 练习：\\\\ e^x \\ = \\ \\sum\_\{i\}\\frac\{x^i\}\{i!\}\\\\ ln(1-x) \\ = \\ - \\sum\_\{i\\ge 1\} \\frac\{x\}\{i\} \\\\ cos(x) \\ = \\ \\sum\_\{i\} \\frac\{(-1)^ix^\{2i\}\}\{(2i)!\} \\\\ sin(x) \\ = \\ \\sum\_\{i\} \\frac\{(-1)^ix^\{2i+1\}\}\{(2i+1)!\} \\\\ \\frac\{1\}\{(1-x)^k\} \\ = \\ \\sum\_\{i\}(^\{k+i-1\}\_i)x^i \\\\ \\\]  
可以证明一个表达式：  
\\\[ e^\{\\pm ix\} = cos(x) \\pm isin(x) \\\]  
这指出\$e^\{ix\}\$对应的复平面上的点是 \$(cos(x),sin(x))\$ ，另外得到欧拉公式：  
\\\[ e^\{\\pi i \} + 1 = 0 \\\]  
有：  
\\\[ e^\{2\\pi i\} = 1 \\\]  
定义n次单位根\$x^n = 1\$ 为满足的\$n\$个复数

一个可行的方式是$\\omega\_n  =  e^\{2 \\pi i /n\} $ ，在复数平面上，形成了一个乘法的循环，即\$\\omega\_n^k = \\omega\_n^\{k \\ mod \\ n\}\$

![JKr+Mm8cf+IAAAAASUVORK5CYII=][JKr_Mm8cf_IAAAAASUVORK5CYII]

性质：  
1.消去引理：$ \\omega\_\{dn\}^\{dk\} = \\omega\_n^k ，d \\neq 0$

2.折半引理： n次单位跟平方的集合 = n/2次单位根平方的集合

3.求和引理(等比数列求和即可证明) ：  
\\\[ \\frac\{1\}\{n\}\\sum\_\{i\}^\{n-1\}\\omega^\{ij\}\_n \\ = \\begin\{cases\} 1 & j \\ mod \\ n = 0\\\\ 0 & j \\ mod \\ n !=0\\\\ \\end\{cases\} \\\]  
**DFT**

1.概念：

DFT,IDFT,矩阵(定义，转置，乘法，初等变换(换法，倍法，消法)，逆矩阵(存在性))，逆矩阵(求和引理)

定义 $A(x) = \\sum\_\{i\}^\{n-1\} a\_ix^i $ 的DFT为点值表达：\$((w\_n^0,y\_0),\\cdots,(w\_n^\{n-1\},y\_\{n-1\} ))\$

反过来可以对一个点值表达定义求表达，称为IDFT

用矩阵表达:$Y = VA \\Rightarrow A = V^\{-1\}Y $

$A\_i = a\_i, Y\_i = y\_i , V\_\{i,j\}  =   w\_n^\{ij\} $

根据求和引理：$V^\{-1\}*\{ij\} =\\frac\{w*\{n\}^\{-ij\} \}\{n\} $

完整写一下DFT和IDFT就是  
\\\[ y\_j \\ = \\ \\sum\_\{i=0\}^\{n-1\} a\_i w\_n^\{ij\} \\\\ y\_j \\ = \\ \\frac\{1\}\{n\} \\sum\_\{i=0\}^\{n-1\} a\_i w\_n^\{-ij\} \\\\ \\\]  
2.求法：(\$A\_0,A\_1\$，折半引理，蝴蝶操作)

两个式子本质上是一样的，考虑求第一个：  
对于A(x)，构造  
\\\[ A\_0 (x) = a\_0 + a\_2 x^2 + \\cdots + a\_\{n-2\}x^\{n/2-1\} \\\\ A\_1 (x) = a\_1 + a\_3 x^2 + \\cdots + a\_\{n-1\}x^\{n/2-1\} \\\\ \\Rightarrow A(x) = A\_0(x^2) + xA\_1(x^2) \\\\ 根据折半引理，问题规模大小就被我们减到了一半 \\\\ 具体实现，只需要翻转系数的二进制位就可以了 \\\\ \\\]

//len为多项式次数界，2^L = len , C 为自定义复数 for(int i = 0;i < len; i++) R[i] = R[i>>1]>>1 | (i&1) << (L-1) ; void FFT(C *a,int f) {//f = 1/-1 ,正/逆变换 for(int i = 0; i < len; i++) if(i < R[i]) swap(a[i],a[R[i]]); for(int i = 1; i < len; i<<=1) { C wn(cos(pi/i),f * sin(pi/i)); for(int j = 0; j < len; j+=(i<<1)) { C w(1,0); for(int k = 0; k < i; k++,w*=wn) { C x = a[j + k],y = w * a[j + i + k]; a[j + k] = x + y,a[j + i + k] = x - y; } } } if(f==-1) for(int i = 0; i < len; i++) a[i] /= len; }

**NTT**

使用于运算在mod P 的意义下进行

如果n | P -1 , 令 G 为 P 的原根，

**MTT**

处理不是ntt模数的情况

拆系数ntt:

按照二进制拆成前15位和后15位，分别相乘

构造 \$P(x) = A(x) + iB(x) , Q(x) = A(x) - iB(x)\$

简单推导结论：\$dft \\ Q\_k \\ = \\ dft \\ P\_\{n-k\}\$

另外还有三模数ntt(不会。。。)

**例题**

1.[通串的匹配问题][Link 1]

2.[loj6434 神仙的游戏][loj6434]

3.[bzoj3992 序列统计][bzoj3992] (原根)

**分治FFT**

1.[普通形式模板][Link 2]

2.f = f 卷 f 的形式，直接做会有问题

只会在l = 左边界的时候有点问题，不妨直接不确定的那部分系数去掉

当 l 是不是边界的时候将贡献/2，在分治的最底层乘回来

3.两道可以感受分治ntt的好题：

[cd 848E Days of Floral Colours][]　(1)

[uoj401 青蕈领主][uoj401] (2)

**FWT FMT FST**

1.问题，基本思想，构造的东西

[可以参考][Link 3]

[AGC034F RNG and XOR][]

[cf1119H Triple][]

[uoj348 周区划分][uoj348]

**循环卷积与n进制异或fwt**

(考虑FFT系数超出设置的len会怎么样？)

[JZOJ6239][]

同样我们根据最高位分类：\$A\_0,A\_1,\\cdots,A\_\{n-1\}\$

考虑只有一维的情况，需要找到一个变换

使得变换->点乘->逆变换之后得到的是mod n的加法

可以联想到循环卷积，直接令变换的矩阵为V即可

和fwt同理扩展到很多维就可以了

## 生成函数和多项式 ##

1.定义

[策爷的课件][Link 4]

OGF EGF ，加法乘法的意义

2.例子：

二进制数,背包的计数理解OGF的拼接

置换的计数,无向图计数理解序列EGF的拼接

3.[多项式相关][Link 5]：  
0.预备知识：高中数学，部分高等数学

多项式求导，多项式积分

1.多项式求逆，多项式开根

[bzoj3625 小朋友和二叉树][bzoj3625]

分治fft很多时候都多项式求逆做

2.多项式ln

[luogu U79666 树上深度博弈][luogu U79666]

3.牛顿迭代，多项式exp ，多项式求幂

[luogu 4389 付公主的背包][luogu 4389]

[uoj50 链式反应][uoj50]

4.多项式除法，取模

常系数线性齐次递推 (\*)

(行列式定义，的五点性质：转置，换法(推)，倍法(推)，分拆(推出展开)，消法)

[luogu 4723 线性递推模板][luogu 4723]

5.多点求值和快速插值( \*)

[uoj182 a^-1 + b problem][uoj182 a_-1 _ b problem]

6.拉格朗日反演 (\*)  
\\\[ f(g(x)) = g(f(x)) = x ，即：f是g的复合逆\\\\ \[x^n\]f(x) = \\frac\{1\}\{n\}\[x^\{n-1\}\](\\frac\{x\}\{f(x)\})^n \\\\ 推广形式： \[x^n\]h(g(x)) = \\frac\{1\}\{n\}\[x^\{n-1\}\]h'(x)(\\frac\{x\}\{f(x)\})^n \\\\ \\\]  
 [bzoj3684 大朋友和二叉树][bzoj3684]

这里有一篇十分通俗的微分doc :  
[一阶微分方程解法][Link 6]

## 数论 ##

**基本定理**

[完全剩余系性质][Link 7]

威尔逊定理：  
\\\[ p是质数 \\Leftrightarrow (p - 1)! \\equiv -1 (mod \\ p)\\\\ \\\]  
费马小定理：  
\\\[ p 是质数,a不整除p \\Rightarrow a^\{p-1\} \\equiv 1 (mod p) \\\]  
欧拉定理：(积性函数，线筛)  
\\\[ phi(p)定义为1 \\to p-1和p 互质的数的个数　\\\\ 如果p = \\prod\_\{i=1\}^\{m\} a\_i^\{b\_i\} , \\phi(p) = p \\prod\_\{i=1\}^\{m\} (1-\\frac\{1\}\{a\_i\}) \\\\ 欧拉定理描述为：\\\\ (a,p) = 1 \\Rightarrow a^\{\\phi(p) \} \\equiv 1 (mod \\ p ) \\\\ \\\]  
勒让得定理：  
\\\[ n!的唯一分解中质因p的个数为：\\\\ \\sum\_\{k\\ge1\}\\lfloor \\frac\{n\}\{p^k\} \\rfloor \\\\ \\\]  
中国剩余定理(CRT)：  
\\\[ \\begin\{cases\} x \\equiv a\_1 (mod \\ m\_1) \\\\ x \\equiv a\_2 (mod \\ m\_2) \\\\ \\vdots \\\\ x \\equiv a\_n (mod \\ m\_n) \\\\ \\end\{cases\} \\\\ 当m\_1,m\_2,\\cdots,m\_n两两互质一定有解为：\\\\ x \\equiv \\sum\_\{i=1\}^\{m\}a\_iM\_iM\_i^\{-1\} (mod \\ M) \\\\ 其中M=\\prod\_\{i=1\}^\{n\}m\_i ，M\_i = \\prod\_\{j=1,j \\neq i\}^\{n\}m\_j\\\\ M\_i^\{-1\}M\_i \\equiv 1 (mod \\ m\_i) \\\\ \\\]  
扩展CRT：\$m\_1,m\_2,\\cdots,m\_n\$不满足两两互质；  
(百度的第一篇博客推法思路大致是的，但是里面有很多多余的步骤?)  
\\\[ 只需要考虑如何解： \\begin\{cases\} x \\equiv a\_1 (mod \\ m\_1) \\\\ x \\equiv a\_2 (mod \\ m\_2) \\\\ \\end\{cases\}　\\\\ x = k m\_1 + a\_1 \\\\ \\Rightarrow km\_1 = a\_2 - a\_1 (mod \\ m\_2) \\\\ 有解的充要条件是:(m\_1,m\_2) | a\_2 - a\_1 \\\\ \\Rightarrow k\\frac\{m\_1\}\{(m\_1,m\_2)\} = \\frac\{a\_2 - a\_1\}\{(m\_1,m\_2)\} (mod \\ \\frac\{m\_2\}\{(m\_1,m\_2)\})　\\\\ \\Rightarrow k = \\frac\{a\_2 - a\_1\}\{(m\_1,m\_2)\}(\\frac\{m\_1\}\{(m\_1,m\_2)\})^\{-1\} (mod \\ \\frac\{m\_2\}\{(m\_1,m\_2)\}) \\\\ 我们右边 = t ,则有k = k'\\frac\{m\_2\}\{(m\_1,m\_2)\} + t \\\\ x = k m\_1 + a\_1 ＝　k'\\frac\{m\_1m\_2\}\{(m\_1,m\_2)\} + tm\_1 + a\_1 \\\\ 即: x \\equiv (inv(\{m\_1\\over (m\_1,m\_2)\},\{m\_2\\over (m\_1,m\_2)\})\*\{(a\_2-a\_1)\\over (m\_1,m\_2)\})\\%\{m\_2\\over (m\_1,m\_2)\}\*m\_1+a\_1 (mod \\ \\frac\{m\_1m\_2\}\{(m\_1,m\_2)\}) \\\\ \\\]  
**素数判定和大整数分解**

Miller-Rabin

1.理论基础：

1)费马小定理的逆定理

有一定概率不成立，我们称这样的p为伪素数

2)二次探测定理：

$p是素数，x^2 \\equiv 1 (mod  p ) \\Rightarrow x \\equiv -1  or  1 (mod  p) $

2.算法流程 miller\_rabin(long long n)：

1)随机一个数字$a < n $, 设 \$u\$ 是 \$n - 1\$ 除去\$2\$的次幂剩下的数

2)对 \$a^\{u\}\$ 和 \$a^\{2u\}\$ 做二次探测并不断令\$u = 2u\$ 直到$ u = n -1$

3)对\$a^u\$ 即 \$a^\{n-1\}\$检验费马小定理

可以多做几次．

Pollard-Rho

1.理论基础：  
1)[生日悖论][Link 8]

2)floyd判环法

相遇后，令一个指针不动，另一个回到起点二者同速运动可巧妙找到环的起点

2.算法流程 pollard-rho(long long n) :  
1)miller-rabin(n)检测成功则退出，否则进入2)尝试找到一个非平凡因子

2)用$ x\_\{i\} = (x\_\{i-1\}^2 + c)  mod   (n-1) + 1 $ 生成伪随机数

判断\$gcd(x\_i - y ,n )\$是否是非平凡因子，是则退出

在\$i\$是２的幂处记录\$y = x\_i\$，在\$2i\$处更新\$y\$，其间如果有\$x\_\{(i+1) \\to 2i\} = y\$则说明出现了环

这样做[据说][Link 9]是\$O(n^\{\\frac\{1\}\{4\}\})\$的 ，我不会证

另：O(1)快速乘法

inline long long multi(long long x,long long y,long long mod) { long long tmp=(x*y-(long long)((long double)x/mod*y+eps)*mod); return tmp<0 ? tmp+mod : tmp; } eps 是用来设置精度的 虽然快但是比较容易炸精度，慎用．．．

**二次剩余**

1.判定：

二次剩余的个数为\$\\frac\{p-1\}\{2\}\$

勒让徳符号 \$(\\frac\{a\}\{p\}) = a^\{\\frac\{p-1\}\{2\}\}\$ (a<p)

欧拉判别法：  
\\\[ a 是 0 的充分必要条件是(\\frac\{a\}\{p\}) = 0\\\\ a 是 p 的二次剩余的充分必要条件是(\\frac\{a\}\{p\}) \\equiv 1 (mod \\ p) \\\\ a 是 p 的二次非剩余的充分必要条件是(\\frac\{a\}\{p\}) \\equiv -1 (mod \\ p) \\\\ \\\]  
(证明：先用费马小证=１的必要以及二分性，再配对反证充分性)

2.(\*)求法：[cipolla算法][cipolla]

解：$x^2 \\equiv n (mod  p) $

考虑随机一个\$p\$的二次非剩余$a^2 - n $

定义一个新的数域(类似复数域)令\$w = \\sqrt\{a^2 - n\}\$

则\$x = \\pm (a+w)^\{\\frac\{p+1\}\{2\}\}\$  
\\\[ \\begin\{align\} &(a+w)^\{p+1\}\\\\ &= (a+w)^p (a+w) \\\\ &= (a^p+w^p)(a+w) \\\\ &= (a-w)(a+w) \\\\ &= a^2 - w^2 \\\\ &= n \\\\ \\end\{align\} \\\]  
最后结果里面的x虚部一定是0，据说是因为由拉格朗日定理\$f(x) \\equiv 0\$在mod p 的数域下最多只有f(x)的最高次数那么多个根，我也不知道为什么．．．．．

**组合数**

1.部分组合恒等式：  
\\\[ \\begin\{align\} &定义可得:\\\\ &1) \\ (^n\_m) = (^\{n-1\}\_\{m-1\}) + (^\{n-1\}\_\{m\})\\\\ &2) \\ (^\{n+1\}\_m) = \\frac\{n+1\}\{n-m+1\}(^\{n\}\_\{m\}) \\\\ &3) \\ (^n\_\{m+1\}) = \\frac\{n-m\}\{m+1\}(^\{n\}\_\{m\}) \\\\ &4) \\ (^\{n+1\}\_\{m+1\}) = \\frac\{n+1\}\{m+1\}(^n\_m) \\\\ &下面要讲的二项式定理可以推：\\sum\_\{i=0\}^n(^n\_i) = 2^n \\\\ &\\sum\_\{i=0\}^\{min(a,b)\}(^a\_i)(^b\_i) = (^\{a+b\}\_b) \\Rightarrow \\sum\_\{i=0\}^n(^n\_i)^2 = C\_\{2n\}^n\\\\ &组合数的一个竖列和斜列都是可以化简的：\\\\ &1)\\sum\_\{i=0\}^\{k\}(^\{n+i\}\_\{m+i\}) = (^\{n+k+1\}\_\{m+k\}) - (^n\_\{m-1\}) \\\\ &2)\\sum\_\{i=0\}^\{k\}(^\{n+i\}\_\{m\}) = (^\{n+k+1\}\_\{m+1\})-(^n\_\{m+1\}) \\\\ \\end\{align\} \\\]  
２.二项式定理  
\\\[ (a＋b)^n = \\sum\_\{i=0\}^\{n\} (^n\_i)a^ib^\{n-i\} \\\\ \\\]  
这个可以归纳证.

３.lucas定理  
\\\[ p是素数，设n = sp+q,m = tp+r (q,r<p)\\\\ 则：\\\\ (^n\_m) \\equiv (^s\_t)(^q\_r) \\\\ \\\]  
这个可以在p进制下扩展

可以构造\$(1+x)^n\$ 利用二项式定理证明

４.[扩展lucas][lucas] :

[bzoj4830 抛硬币][bzoj4830]

**bsgs**  
\\\[ \\begin\{align\} &求：A^x \\equiv B (mod \\ C)的最小非负整数解，满足(A,C)=1\\\\ &(A,C)=1 \\Rightarrow A^x\\equiv A^\{x \\ mod \\ \\phi(c)\} (mod \\ C)\\\\ &那么令m = \\lceil \\sqrt C \\rceil ，A^\{im-j\} \\equiv B(mod \\ C)\\\\ &(A^\{m\})^i \\equiv A^jB(mod \\ C)\\\\ &用hash表存下右边,枚举左边即可求解 \\\\ \\end\{align\} \\\]  
时间复杂度：\$O(\\sqrt C 或 \\sqrt C log \\sqrt C)\$

扩展bsgs  
\\\[ 问题一样，只是没有(A,C) = 1 ，这是就没有欧拉定理了 \\\\ 首先判掉B = 1,0的情况 ,考虑不断除去a 和模数的gcd：\\\\ 设D = \\prod\_\{i=1\}^\{k\}d\_i,其中d\_i表示第i次求得a和模数的gcd\\\\ A^\{x-k\} \\frac\{A^k\}\{D\} \\equiv \\frac\{B\}\{D\} (mod \\ \\frac\{C\}\{D\})\\\\ 枚举x = 1 \\to k ，x > k 的移项之后可以直接bsgs \\\]  
**线性代数**

1.矩阵

高斯-亚当消元求逆矩阵(满秩)

线性相关/无关，张成，基

线性基

插入，合并，询问最大/最小值，查询排名，查询第k小

[bzoj 2844 albus就是要第一个出场][bzoj 2844 albus]

[bzoj3569 DZY Loves Chinese II][]

[你们哪天看懂了证明记得告诉我][Link 10]

2.行列式  
\\\[ det(A) = \\sum\_\{P\} (-1)^\{\\tau(P)\} \\prod\_\{i=1\}^\{n\} A\_\{i,p\_i\}\\\\ \\\]  
 性质：

1.初等变换：1 2 3

2.\$det(A^\\tau) = det(A)\$

3.\$det(A) = det(A)det(B)\$

证明：[拉普拉斯定理][Link 11]

Matrix - tree 定理 (K=D-A)

[2016级的\*ZJ学长][2016_ZJ]

[BEST定理][BEST]

## 群论 ##

1.群的判定：

(a)封闭性：任意\$a,b\\in G\$ ，存在\$c \\in G,a \\cdot b=c\$

(b)结合律：任意$a,b,c\\in G \$，满足\$(a \\cdot b)\\cdot c = a \\cdot (b \\cdot c) $

(c)单位元：存在\$e \\in G\$，对任意\$a \\in G\$，满足\$a \\cdot e = e \\cdot a = a\$

(d)逆元：对任意\$a \\in G\$，存在\$b \\in G\$，\$a \\cdot b = b \\cdot a = e\$，记做\$b = a^\{-1\}\$

(置换，置换的乘法，置换群)

2.burnside 引理  
\\\[ \\begin\{align\} &L = \\frac\{1\}\{|G|\}\\sum\_\{j=1\}^\{s\}D(a\_j)\\\\ &其中L表示本质不同的元素个数，G表示置换群为\\\{a\_1,\\cdots,a\_s\\\},\\\\ &D(a\_j)表示置换a\_j下的不动点个数\\\\ &证明：\\\\ &引理1：定义稳定核G(c)为集合\\\{f|f \\cdot c = c ,c \\in G\\\} ，它是一个群\\\\ &引理2: 和c本质相同的方案数：\\frac\{|G|\}\{G(c)\}\\\\ &证明：\\\\ & \\ \\ 若f,g,c \\in G \\ 则 \\ f \\cdot c = g \\cdot c \\Leftrightarrow f^\{-1\}g \\in G(c) \\\\ & \\ \\ 那么对于一个f ，和它作用相同的置换g的集合是\\\{f \\cdot h | h \\in G(c)\\\} \\\\ & \\ \\ 那么和c 本质相同的方案数为\\frac\{|G|\}\{|G(c)|\}\\\\ &立即推出：|G(c)| = \\frac\{|G|\}\{|等价类(c)|\}\\\\ &对f\\cdot c=c的(f,c)计数\\\\ &1) \\sum\_\{j=1\}^\{s\}D(a\_j)\\\\ &2) \\sum\_\{i=1\}^\{n\}|G(c)| = \\sum\_\{i=1\}^\{n\}\\frac\{|G|\}\{|等价类|\} = L|G|\\\\ &最后一步是一起考虑一个等价类的贡献，1)和2)相等即推出burnside引理！ \\end\{align\} \\\]  
3.polya 定理

每个置换都可以写成若干个互不相交的循环的乘积

设G是一个n阶置换的群，用m种颜色去涂：  
\\\[ L\\ = \\ \\frac\{1\}\{G\}(m^\{c(g\_1)\} + m^\{c(g2)\}+\\cdots+m^\{c(g\_n)\}) \\\\ \\\]  
其中\$g\_i \\in G\$，\$c(g\_i)\$为\$g\_i\$中循环的个数

[luogu 4916 魔力环][luogu 4916]

## prufer 序列 ##

有标号无根树

生成，性质，还原

[bzoj1005 明明的烦恼][bzoj1005]

## 概率论 ##

我理论部分基本空白，只知道一些结论：

\$f(x)\$在\$\[L,R\]\$的期望  
\\\[ \\begin\{align\} 如果x是一个\[L,R\]均匀分布的随机变量\\\\ E(f(x)) \\ = \\ \\frac\{\\int\_\{L\}^\{R\} f(x) \\ dx\}\{R-L\} \\\\ \\end\{align\} \\\]  
贝叶斯公式  
\\\[ P(A|B) = \\frac\{P(B|A)P(A)\}\{P(B)\} \\\\ \\\]  
[uoj299 游戏][uoj299]

**博弈论**

．．．．

重点理解sg函数

## 容斥和反演 ##

**基本形式**：  
\\\[ \\begin\{align\} ans = \\sum\_if(i)a\_i \\\\ \\end\{align\} \\\]  
**组合数容斥**  
\\\[ \\begin\{align\} &f(i) = (-1)^i\\\\ &\\sum\_\{i=0\}^\{n\}(-1)^i(^n\_i) = \[n=0\] \\\\ &因为：(或者直接考虑(1-1)^n)\\\\ &\\begin\{cases\} 当n = 0,显然= 1\\\\ 当n \\gt 0:原式= \\sum\_\{i=0\}^\{n-1\}(-1)^\{i+1\}(^\{n-1\}\_i) + \\sum\_\{i=0\}^\{n-1\}(-1)^i(^\{n-1\}\_i) = 0\\\\ \\end\{cases\} &\\end\{align\} \\\]  
[loj2351 毒蛇越狱][loj2351]

**二项式反演**   
\\\[ f(n) = \\sum\_\{i=0\}^\{n\}(^n\_i)g(i) \\Leftrightarrow g(n) = \\sum\_\{i=0\}^\{n\}(-1)^\{n-i\}(^n\_i)f(i)\\\\ 另一种更好看的形式：\\\\ f(n) = \\sum\_\{i=0\}^\{n\}(-1)^\{i\}(^n\_i)g(i) \\Leftrightarrow g(n) = \\sum\_\{i=0\}^\{n\}(-1)^\{i\}(^n\_i)f(i)\\\\ 另一种不太好看的形式：\\\\ f(i) = \\sum\_\{j\\ge i\}(^j\_i)g(j) \\Leftrightarrow g(i) = \\sum\_\{j \\ge i\}(-1)^\{j-i\}(^j\_i) f(j) \\\\ \\\]  
[经典的错排问题][Link 12]

[loj3120 珍珠][loj3120]

**斯特林容斥**  
\\\[ \\begin\{align\} &f(i) = (-1)^\{i-1\}(i-1)! \\\\ &\\sum\_\{i=1\}^\{n\}\\\{^n\_i\\\}(-1)^\{i-1\}(i-1)! = \[n=1\] \\\\ &因为：\\\\ &\\begin\{cases\} 当n = 1，显然 = 1\\\\ 当n \\gt 1,原式 = \\sum\_\{i=1\}^\{n-1\}(-1)^\{i-1\}i!\\\{^\{n-1\}\_\{i\}\\\}+\\sum\_\{i=1\}^\{n-1\}(-1)^ii!\\\{^\{n-1\}\_\{i\}\\\} = 0\\\\ \\end\{cases\} \\end\{align\} \\\]  
**斯特林数**(定义，递推式，求法 : I 倍增FFT,||卷积，用于转换幂，反转公式)

[bzoj 异或图][bzoj]

[斯特林数][Link 13]

1.定义：  
\\\[ 1.两类数的递推式：\\\\ \[^n\_i\] = \[^\{n-1\}\_\{i-1\}\]+(n-1)\[^\{n-1\}\_i\]\\\\ \\\{^n\_i\\\} = \\\{^\{n-1\}\_\{i-1\}\\\} + i\\\{^\{n-1\}\_i\\\}\\\\ 根据定义 \\sum\_\{i=0\}^\{n\}\[^n\_i\] = n!\\\\ \\\]  
2.斯特林数一行的求法：

第一类：(倍增fft)  
\\\[ \[\_m^n\] = \[x^m\] x^\{\\overline n\}\\\\ 倍增FFT即可 \\\]  
\$O(m \\ log \\ m )\$

第二类：(存在卷积形式)  
\\\[ 根据组合意义可以知道：\\\\ n^m = \\sum\_\{i=0\}^\{m\}(^m\_i)\\\{^n\_i\\\}i!\\\\ 对上面的式子二项式反演或者直接考虑容斥可以得到：\\\\ \\\{^n\_m\\\} = \\frac\{1\}\{m!\}\\sum\_\{i=0\}^\{m\}(-1)^\{m-i\}(^m\_i)i^\{n\}\\\\ 立即推出卷积形式：\\\\ \\\{^n\_m\\\} = \\sum\_\{i=0\}^\{m\}\\frac\{(-1)^\{m-i\}\}\{(m-i)!\}\\frac\{i^\{n\}\}\{i!\}\\\\ \\\]  
\$O(m \\ log \\ m )\$

[bzoj2159 crash的文明世界][bzoj2159 crash]

**斯特林反演**   
\\\[ f(n) = \\sum\_\{i=1\}^\{n\} \\\{^n\_i\\\} g(i) \\Longleftrightarrow g(n) = \\sum\_\{i=1\}^\{n\} (-1)^\{n-i\} \[^n\_i\]f(i)\\\\ f(n) = \\sum\_\{i=1\}^\{n\} \[^n\_i\] g(i) \\Longleftrightarrow g(n) = \\sum\_\{i=1\}^\{n\} (-1)^\{n-i\} \\\{^n\_i\\\}f(i)\\\\ 证明可以应用反转公式:\\\\ \\displaystyle \\sum\_\{k=m\}^n (-1)^\{n-k\}\\begin\{bmatrix\}n\\\\k\\end\{bmatrix\} \\begin\{Bmatrix\}k\\\\m\\end\{Bmatrix\}=\[m=n\]\\\\ \\sum\_\{k=m\}^n (-1)^\{n-k\}\\begin\{Bmatrix\}n\\\\k\\end\{Bmatrix\} \\begin\{bmatrix\}k\\\\m\\end\{bmatrix\}=\[m=n\]\\\\ 反转公式的证明可以应用斯特林数和幂的关系:\\\\ x^n = \\sum\_\{i=0\}^\{n\}\\\{^n\_i\\\}x^\{\\underline i\}\\\\ x^\{\\overline n\} = \\sum\_\{i=0\}^\{n\}\[^n\_i\]x^i\\\\ 这个关系归纳可证，再带入幂的转化关系可证反转\\\\ \\\]  
[我只做过裸题][Link 14]

**容斥系数**   
\\\[ 本质是我们只需要满足\\\\ \\sum\_\{i\}^\{n\}f(i)g(i) = \\delta\_n \\\\ g，\\delta是确定的，所以我们可以直接O(n^2)解出f\\\\ 或者可以直接反演求出f,某些情况或者可以用生成函数推出f\\\\ 或者：直接打表鸭！\\\\ \\\]  
[玲珑杯线上赛河南专场　Round\#17 B][Round_17 B]

**min-max容斥**  
\\\[ \\max(S)=\\sum\_\{T\\subseteq S\} (-1)^\{|T|-1\}\\min(T)\\\\ E(\\max S)=\\sum\_\{T\\subseteq S\} (-1)^\{|T|-1\}E(\\min T)\\\\ \\text\{lcm\}(S)=\\prod\_\{T\\subseteq S\} (-1)^\{|T|-1\}\\gcd(T)\\\\ min和max当然是对称的\\\\ \\\]  
[loj2542 随机游走][loj2542]

[luogu4704 重返现世][luogu4704]

kth min-max容斥  
\\\[ 推容斥系数的技巧可以用了：\\\\ \[i=k\] = \\sum\_\{j=1\}^\{i\}(^\{i-1\}\_\{j-1\})f(j) \\\\ 二项式反演得：\\\\ f(i) = \\sum\_\{j=1\}^\{i\}(-1)^\{i-j\}(^\{i-1\}\_\{j-1\})\[j==k\] \\\\ 即f(i) = (-1)^\{i-k\}(^\{i-1\}\_\{k-1\}) \\\\ kthmax(S) = \\sum\_\{T \\subset S\} (-1)^\{|T|-k\}(^\{|T|-1\}\_\{k-1\})min(T) \\\]  
**子集反演**  
\\\[ f(S) = \\sum\_\{T \\subset S\}g(T) \\Leftrightarrow g(S) = \\sum\_\{T \\subset S\}(-1)^\{|S|-|T|\}f(T)\\\\ f(S) = \\sum\_\{S \\subset T\}g(T) \\Leftrightarrow g(S) = \\sum\_\{S \\subset T\}(-1)^\{|T|-|S|\}f(T)\\\\ \\\]  
[loj 2983 数树][loj 2983]

**单位根反演**   
\\\[ \\frac\{1\}\{n\}\\sum\_\{j=0\}^\{n-1\}\\omega\_n^\{j(i-t)\} = \[i \\% n=t\]\\\\ \\\]  
[loj6485 LJJ学二项式定理][loj6485 LJJ]

[loj3058 白兔之舞][loj3058]

**莫比乌斯反演**   
[Po姐的ppt][Po_ppt]

莫比乌斯函数：

1.定义  
\\\[ \\mu(n) = \\begin\{cases\} 1 &n=1\\\\ (-1)^r & n=p\_1\\cdots p\_r,p\_1\\cdots p\_r 是两两不同的质数\\\\ 0 &其它，即n有大于1的平方因子\\\\ \\end\{cases\}\\\\ \\\]  
2.性质：  
\\\[ \\begin\{align\} &1)积性\\\\ &2)\\sum\_\{d|n\} \\mu(d) = \[n=1\] \\\\ &3)\\sum\_\{d|n\}\\frac\{\\mu(d)\}\{d\}=\\frac\{\\phi(n)\}\{n\}\\\\ &(考虑\\sum\_\{i=1\}^\{n\}\[gcd(i,n)=d\] = \\phi(\\frac n d) 即可证3)\\\\ \\end\{align\} \\\]  
反演的两种形式：  
\\\[ f(n) = \\sum\_\{d|n\} g(d) \\Leftrightarrow g(n) = \\sum\_\{d|n\}\\mu(\\frac\{n\}\{d\})f(d)\\\\ f(n) = \\sum\_\{n|d\} g(d) \\Leftrightarrow g(n) = \\sum\_\{n|d\}\\mu(\\frac\{d\}\{n\})f(d)\\\\ \\\]  
[bzoj2820 YY的GCD][bzoj2820 YY_GCD]

[bzoj3434 时空穿梭][bzoj3434]

[loj 2085 循环之美][loj 2085]

[OIwiki !][OIwiki]

(大家可能只有自行学习杜教筛，洲阁筛，和min25筛了)

杜教筛的复杂度，我当时学的时候一直没有搞清楚有一点，后来看rqy的博客看到了：  
\\\[ O(\\sum\_\{i=1\}^\{\\sqrt n\} \\sqrt \\frac\{n\}\{i\}) \\approx O(2\\sqrt\{n\}\\int\_0^\{\\sqrt n\}i^\{\\frac\{1\}\{2\}\}) = O(n^\{\\frac\{3\}\{4\}\})\\\\ \\\]  
(由于没时间讲计算几何了，大家记得学一下闵可夫斯基和)

转载于:https://www.cnblogs.com/Paul-Guderian/p/11275126.html

[JKr_Mm8cf_IAAAAASUVORK5CYII]: 
[Link 1]: https://www.cnblogs.com/cjyyb/p/8798446.html
[loj6434]: https://loj.ac/problem/6436
[bzoj3992]: https://www.lydsy.com/JudgeOnline/problem.php?id=3992
[Link 2]: https://www.luogu.org/problem/P4721
[cd 848E Days of Floral Colours]: http://codeforces.com/problemset/problem/848/E
[uoj401]: http://uoj.ac/problem/401
[Link 3]: https://www.cnblogs.com/Paul-Guderian/p/10826888.html
[AGC034F RNG and XOR]: https://atcoder.jp/contests/agc034/tasks/agc034_f
[cf1119H Triple]: http://codeforces.com/contest/1119/problem/H
[uoj348]: http://uoj.ac/problem/348
[JZOJ6239]: https://www.cnblogs.com/Paul-Guderian/p/11149081.html
[Link 4]: https://wenku.baidu.com/view/3ce4b1d6b0717fd5360cdc97.html?pn=1
[Link 5]: https://www.cnblogs.com/ywwyww/p/8511505.html
[bzoj3625]: https://www.lydsy.com/JudgeOnline/problem.php?id=3625
[luogu U79666]: https://www.luogu.org/problem/U79666
[luogu 4389]: https://www.luogu.org/problem/P4389
[uoj50]: http://uoj.ac/problem/50
[luogu 4723]: https://www.luogu.org/problem/P4723
[uoj182 a_-1 _ b problem]: http://uoj.ac/problem/182
[bzoj3684]: https://www.lydsy.com/JudgeOnline/problem.php?id=3684
[Link 6]: https://wenku.baidu.com/view/5842f96fb84ae45c3b358c53.html
[Link 7]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E5%89%A9%E4%BD%99%E7%B3%BB/3712670?fr=aladdin
[Link 8]: https://baike.baidu.com/item/%E7%94%9F%E6%97%A5%E6%82%96%E8%AE%BA/2715290?fr=aladdin
[Link 9]: https://blog.csdn.net/qq_39972971/article/details/82346390
[cipolla]: https://blog.csdn.net/a_crazy_czy/article/details/51959546
[lucas]: https://blog.csdn.net/clove_unique/article/details/54571216/
[bzoj4830]: https://www.lydsy.com/JudgeOnline/problem.php?id=4830
[bzoj 2844 albus]: https://www.lydsy.com/JudgeOnline/problem.php?id=2844
[bzoj3569 DZY Loves Chinese II]: https://www.lydsy.com/JudgeOnline/problem.php?id=3569
[Link 10]: http://wuhongxun.blog.uoj.ac/blog/3003
[Link 11]: https://wenku.baidu.com/view/0c0b42fd770bf78a65295430.html
[2016_ZJ]: https://www.cnblogs.com/zj75211/p/8039443.html
[BEST]: https://www.cnblogs.com/Paul-Guderian/p/10294032.html
[luogu 4916]: https://www.luogu.org/problem/P4916
[bzoj1005]: https://www.lydsy.com/JudgeOnline/problem.php?id=1005
[uoj299]: http://uoj.ac/problem/299
[loj2351]: https://loj.ac/problem/2351
[Link 12]: https://www.cnblogs.com/ww3113306/p/10114679.html
[loj3120]: https://loj.ac/problem/3120
[bzoj]: https://www.lydsy.com/JudgeOnline/problem.php?id=4671
[Link 13]: https://www.cnblogs.com/hchhch233/p/10016543.html
[bzoj2159 crash]: https://www.lydsy.com/JudgeOnline/problem.php?id=2159
[Link 14]: https://www.cnblogs.com/Paul-Guderian/p/10519990.html
[Round_17 B]: https://www.ifrog.cc/acm/problem/1138
[loj2542]: https://loj.ac/problem/2542
[luogu4704]: https://www.luogu.org/problem/P4707
[loj 2983]: https://loj.ac/problem/2983
[loj6485 LJJ]: https://loj.ac/problem/6485
[loj3058]: https://loj.ac/problem/3058
[Po_ppt]: https://wenku.baidu.com/view/808798e777eeaeaad1f34693daef5ef7ba0d12ff.html
[bzoj2820 YY_GCD]: https://www.luogu.org/problem/P2257
[bzoj3434]: https://www.lydsy.com/JudgeOnline/problem.php?id=3434
[loj 2085]: https://loj.ac/problem/2085
[OIwiki]: https://oi-wiki.org/math/mobius/