Day_1 计数
它咕掉了
Day_1 序列数据结构
它咕掉了
Day_2 线性代数
高斯消元\Large{高斯消元}高斯消元
普通版：略
模质数：求逆
模合数：exgcd
逆矩阵\Large{逆矩阵}逆矩阵
AA−1=I=[10⋯001⋯0⋮⋮⋱⋮00⋯1]
AA^{-1}=I=\left[
\begin{matrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 \\
\end{matrix}
\right]
AA−1=I=⎣⎢⎢⎢⎡10⋮001⋮0⋯⋯⋱⋯00⋮1⎦⎥⎥⎥⎤
怎么求：高斯消元，左边消元的过程中对应修改右边的矩阵。
有何用：解一个或多个形如A⋅x=bA\cdot x=bA⋅x=b的方程（两边同时乘上A−1A^{-1}A−1）bbb为向量
多个也可理解为解A⋅x=BA\cdot x=BA⋅x=B的方程。BBB为矩阵
矩阵快速幂\Large{矩阵快速幂}矩阵快速幂
行列式\Large{行列式}行列式
A=[abcdefghi]
A=\left[\begin{array}{}
a & b & c \\
d & e & f \\
g & h & i
\end{array}\right]
A=⎣⎡adgbehcfi⎦⎤
D=∣A∣=det(A)=∣abcdefghi∣
D=|A|=det(A)=\left|\begin{array}{} a & b & c \\ d & e & f \\ g & h & i \end{array}\right|
D=∣A∣=det(A)=∣∣∣∣∣∣adgbehcfi∣∣∣∣∣∣
det(A)=∑σ∈Sndet(A)=\sum_{\sigma \in S_n}det(A)=∑σ∈Snff
det(AB)=det(A)⋅det(B)det(AB)=det(A)\cdot det(B) det(AB)=det(A)⋅det(B) "ABABAB"是矩阵乘法
余子式：MijM_{ij}Mij=除去i行j列的行列式
k阶主子式：选kkk行kkk列（标号一样）拿出来组成的k×kk×kk×k的行列式
代数余子式：Cij=(−1)i+j⋅MijC_{ij}=(-1)^{i+j}\cdot M_{ij}Cij=(−1)i+j⋅Mij
→det(A)=Cij⋅aij\to det(A)=C_{ij}\cdot a_{ij}→det(A)=Cij⋅aij
怎么求：高斯消元
nnn个nnn维向量组成的单纯形超空间体积值为：det⋅1n!det\cdot \frac{1}{n!}det⋅n!1
如三维体积为V=16∣x1y1z1x2y2z2x3y3z3∣V=\frac{1}{6}\left|\begin{array}{} x1 & y1 & z1 \\ x2 & y2 & z2 \\ x3 & y3 & z3 \end{array}\right|V=61∣∣∣∣∣∣x1x2x3y1y2y3z1z2z3∣∣∣∣∣∣
矩阵树定理\Large{矩阵树定理}矩阵树定理
矩阵KKK=度数矩阵DDD-邻接矩阵AAA
求det(K)det(K)det(K)的任何一个n−1n-1n−1阶主子式的值都是是生成树的个数。
若有向图，则：
AijA_{ij}Aij表示i到j的边的相反数，GiiG_{ii}Gii表示i的入度，行列式det(K)det(K)det(K)的MiiM_{ii}Mii表示以iii为根的外向树数。
AijA_{ij}Aij表示i到j的边的相反数，GiiG_{ii}Gii表示i的出度，行列式det(K)det(K)det(K)的MiiM_{ii}Mii表示以iii为根的内向树数。
BEST定理\Large{BEST定理}BEST定理
设ec(G)ec(G)ec(G)表示欧拉路径的数量，deg(v)deg(v)deg(v)表示点vvv的入度（入度和出度要相等）， ts(G){t}_{s}(G)ts(G)表示以sss点为根的外向树的个数。有 ec(G)=ts(G)∏v∈V(deg(v)−1)!\large ec(G)=t_s(G)\prod_{v\in V}(deg(v)-1)!ec(G)=ts(G)∏v∈V(deg(v)−1)!
带状矩阵\Large{带状矩阵}带状矩阵
带状矩阵即在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。
带状矩阵高斯消元时间复杂度O(nD2)O(nD^2)O(nD2)，DDD为带宽。。但高斯消元时要向右找非零的数。
线性空间\Large{线性空间}线性空间
线性基\Large{线性基}线性基
拟阵\Large{拟阵}拟阵
…
克莱姆(Cramer)法则\Large 克莱姆(\Large Cramer )法则克莱姆(Cramer)法则
解线性方程用，略
伴随矩阵\Large{伴随矩阵}伴随矩阵
矩阵A的伴随矩阵是A的余子矩阵的转置矩阵，即：adj(A)=CT→[adj(A)]ij=Cjiadj(A)=C^T \to [adj(A)]_{ij}=C_{ji}adj(A)=CT→[adj(A)]ij=Cji
作为拉普拉斯公式的推论，关于n×nn×nn×n的矩阵AAA的行列式有：
Aadj(A)=adj(A)A=det(A)IAadj(A)=adj(A)A=det(A)IAadj(A)=adj(A)A=det(A)I
…
判断二分图是否存在完备匹配\Large 判断二分图是否存在完备匹配判断二分图是否存在完备匹配
若存在，积和式，行列式均不为0。（邻接矩阵，相连的为x部标号，不相连的为0）
Tutte Matrix\Large Tutte\ MatrixTutte Matrix
…
自闭
dlsnb
Day_3 图论
O(nlog2(n)/nlog(n)α(n))O(nlog^2(n)/nlog(n)\alpha(n))O(nlog2(n)/nlog(n)α(n)) …
定义fif_ifi表示1→i1\to i1→i的最短距离，gig_igi表示i→ni\to ni→n的最短距离。
拓扑序枚举，对于xxx，拓扑序为d(x)d(x)d(x)，答案为
mind(u)<d(x)<d(v)fu+gv+w(u,v)\large min_{d(u)<d(x)<d(v)}f_u+g_v+w(u,v)mind(u)<d(x)<d(v)fu+gv+w(u,v)
例3 题解 ：随机，O(n)O(n)O(n) 拓扑传最小值fff，fi=1n+1→n=1fi−1f_i=\frac{1}{n+1}\to n=\frac 1{f_i}-1fi=n+11→n=fi1−1，多做几次精度就准了。
最小生成树，贪心调整…
把矩阵树定理中的数的空间拓宽到kkk次多项式并且用求逆元的方法消元。
注意如果kkk过大就直接代入0..n0..n0..n插值了。
copy的，不会
暴力：枚举权值和(平均值)做MST，时间复杂度O(mlog(m)∑wi)O(mlog(m)\sum w_i)O(mlog(m)∑wi)
暴力2：本质不同的边排列顺序只有m2m^2m2种（只有经过两值中点才会交换顺序），直接枚举然后MST，时间复杂度O(m3log(m))O(m^3log(m))O(m3log(m))。
发现当随着平均值σ\sigmaσ枚举增大，(wi−σ)2(w_i-\sigma)^2(wi−σ)2是形状相同，顶点在x轴上，开口向上的二次函数，一条边如果被后面的其他边替换掉就再也不会回来。
按区间从小到大来求，在两条边大小关系改变时，考察能否用新的小边替换大边使得还是一棵树，也就是不断调整最小生成树，用LCTLCTLCT维护，由于改变次数 O(m2)O(m^2)O(m2)，所以时间复杂度 O(m2log(m))O(m^2log(m))O(m2log(m))，但LCTLCTLCT常数很大。
暴力3：可以发现一条边出现在最小生成树中一定是一段区间，记作[li,ri][l_i, r_i][li,ri]，可以用并查集维护最大生成树求出。求出l,rl,rl,r后，得到O(m)O(m)O(m)个时间点，从小到大扫，在lil_ili处加入边iii，在rir_iri处删除iii。不用维护树的形态。时间复杂度O(m2log(m)))O(m^2log(m)))O(m2log(m)))。
正解：维护树的形态，用LCTLCTLCT维护最大生成树，加入一条边如果不连通，lil_ili就是−inf-inf−inf，联通就在路径上查询边权最小的边j，让li=wi+wj2l_i=\frac{w_i+w_j}2li=2wi+wj，弹出一条边的时候求出rjr_jrj。求出来后用暴力3的方法求答案，时间复杂度O(mlog(m))O(mlog(m))O(mlog(m))
详见《ioi2018候选集训队论文<最小方差生成树>命题报告 何中天》
问题就在如何保证一个集合只选一个，对于每个前缀后缀建辅助点，就可以建图了，类似于优化建图吧
二分答案+拆点2sat 水
…
先考虑<=0，对行列建点。有一个点就行列连边，是一个二分图，跑欧拉回路，从X部到Y部看作黑点，反之白点就行了。
考虑<=1，两边可能有奇点，没有欧拉回路，我们两边分别建一个虚点，向对方的奇点连边，奇点一定是偶数个(两边相等)，所以直接跑欧拉回路。每个行/列最多连一条虚边，所以<=1。
也可以直接把奇点两两配对跑欧拉回路。
先考虑答案＋1，把m条边是否选看作变量，由于要deg为偶数，所有相当于异或为0，则有n个方程。
任意取这个图的生成树，这个秩是<n的，因为所有异或起来为0。
如果有一个n-1阶的小矩阵的行列式不为0，则秩为n-1，整个的秩也就>=n-1。一棵生成树去除根后是n-1*n-1的，剩下的经过一些变换后可以恰好是matrix-tree的形式，行列式绝对值为1(树的生成树为1)不为0，所以证到了m这n个方程的秩为n-1
然后…自闭
又线代了
dlsnb
wjznb
Day_3 字符串
SAM\Large SAMSAM
SAM+线段树合并
SAM
回文树（没学，自闭）来个博客
对于i>1，Si+1一定是Si的一个后缀。所以只需二分长度，然后在SAM上，查询一个串在另一个串中出现次数是否大于2。至于怎么查，不知道。博客
考虑F(∣S∣)−F(∣S∣−1)F(|S|)-F(|S|-1)F(∣S∣)−F(∣S∣−1)，就是回文树上最后一个字母代表的节点与其他所有节点的LCA的长度和…
回文树。不会。
问题也就是询问该串的后缀树上，长度不超过L的…
把求border转化为求period…
。。。
Lyndon串\Large Lyndon串Lyndon串
对于字符串SSS，如果SSS的最⼩后缀是他本身，那么SSS是 LyndonLyndonLyndon串。
sss为LyndonLyndonLyndon串等价于sss本身是其循环移位中最小的⼀ 个
Lyndon分解\Large Lyndon分解Lyndon分解
存在性
唯一性
Duval算法\Large Duval算法Duval算法
…
…
…
Day_4 ACM
ACM赛
做了4道水题，Freopen巨佬做了5道题 -> 排名6 (最高排名 2)
Day_5 树上数据结构
点分治\Large 点分治点分治
法1：括号序列 蒟蒻博客
法2：对于传统树分治做法，就是在每个树分治的分治中心上开个堆维护一下：
• 每个子树一个堆维护到其的最大距离
• 再开个堆维护上面那个堆的前2大值
• 再开个堆维护全局的最大值
• 然后每次暴力更新即可，总复杂度O( (n + m)log^2n )
和之前那个题差不多，对每个颜色分别维护即可
LCT\Large LCTLCT
。。。
动态DP\Large 动态DP动态DP
可以发现只会有一个人会动，且只有遇到的数为(i-ai)%n时才会动。
前i个人肯定不会让x大于等于i。然后我们将i向(i-ai)%n < i 的连边。形成森林。
是一个开枪游戏
如果0活下来就是0
否则是开枪干掉0的编号最小的人
？
LCT/树剖
两棵Splay，一棵维护形态，一棵维护权值
i递增的时候j递减，用LCT维护删除时间最小生成树
//////////////////////////////
。。。。。。。。。。。
11111111111111111111
22222222222222222222
33333333333333333333
44444444444444444444
55555555555555555555
66666666666666666666
77777777777777777777
88888888888888888888
99999999999999999999
10101010101010101010
Day_5 生成函数及多项式
1+x+x2+x3+...+xn+...=11−x1+x+x^2+x^3+...+x^n+... = \frac 1{1-x}1+x+x2+x3+...+xn+...=1−x1
1+x+2x2+3x3+...+nxn+...=1(1−x)21+x+2x^2+3x^3+...+nx^n+...=\frac 1{(1-x)^2}1+x+2x2+3x3+...+nxn+...=(1−x)21
1+x2+x4+...+x2n+...=11−x21+x^2+x^4+...+x^{2n}+...=\frac 1{1-x^2}1+x2+x4+...+x2n+...=1−x21
R(x)=1+x2+x4+...R(x)=1+x^2+x^4+...R(x)=1+x2+x4+...
Y(x)=1+x5+x10+...Y(x)=1+x^5+x^{10}+...Y(x)=1+x5+x10+...
B(x)=1+x+x2+x3+x4B(x)=1+x+x^2+x^3+x^4B(x)=1+x+x2+x3+x4
G(x)=1+xG(x)=1+xG(x)=1+x
指数型\Large 指数型指数型
1+x+x22!+x33!+...=ex1+x+\frac{x^2}{2!}+ \frac{x^3}{3!}+...=e^x1+x+2!x2+3!x3+...=ex
1+x22!+x44!+...=ex+e−x21+\frac{x^2}{2!}+\frac{x^4}{4!}+...=\frac{e^x+e^{-x}}21+2!x2+4!x4+...=2ex+e−x
x+x33!+x55!+...=ex−e−x2x+\frac{x^3}{3!}+\frac{x^5}{5!}+...=\frac{e^x-e^{-x}}{2}x+3!x3+5!x5+...=2ex−e−x
一维循环卷积\Large 一维循环卷积一维循环卷积
FFTFFTFFT
二维循环卷积\Large 二维循环卷积二维循环卷积
对每一维进行DFTDFTDFT
FWT\Large FWTFWT
就是k维循环卷积
把一个n×(n-1)的矩阵设置为类型Mat，Mat的乘法运算定义为二维循环卷积，那么这个图的转移矩阵事实上就是一个n×n的以Mat为值的矩阵，并且可以发现，由于Mat的运算满足交换律，分配律还有结合律，所以转移矩阵的乘法同样可以当成正常矩阵乘法来做。现在我们要做的就是加快这个矩阵乘法的效率。
…没抄完
1163962801 - 1 = 1163962800 = 2^4 * 3^2 * 5^2 * 7 * 11 * 13 * 17 * 19
所以1~10都是它的原根。。。？
组合数贡献可以通过加自环去掉，也就是Len时间再走，其他时间走自环/休息，那么每天路径的贡献都是1。这样的话自环不能算作路经长度。
…生成函数 burnside引理/Polya定理
牛顿迭代\Large 牛顿迭代牛顿迭代
泰勒展开\Large 泰勒展开泰勒展开
多项式求逆\Large 多项式求逆多项式求逆
多项式除法\Large 多项式除法多项式除法
多项式Ln\Large 多项式Ln多项式Ln
多项式exp\Large 多项式exp多项式exp
多项式多点求值
多项式多点插值