高中时期 OI 笔记完全公开（上篇）

2023-12-12

26k words

注意：篇目很长，加载很慢。

偶然间翻到了远古时期 OI 笔记（或者说是日记之类的233），遂发出来以供~~大家嘲笑~~纪念。

后篇（或者可能是中篇+后篇）估计要等到寒假拿到旧设备才能观赏了。

没有经过十分严格的审查，欢迎扒黑历史。

2021.7

6.29（把前几天的补一下orz）

关于博弈问题

没有模型的问题（树上/图上/序列上/〇〇上），分析分析，多半设计状态先（大概也不能完全叫博弈论）

有模型的，，，Bash/Fib/威佐夫（奇异局势相关）/Nim啥有结论就用了转化为其他的题，其他的偏博弈一点的题就SG或N/P爆艹~~（反正大概率草不出来）~~

字典序第k小

经典$k\rightarrow k/k-i$判断的方法，往这方面想，~~然后就有暴力分了~~/kk

手玩一下，构造几次，找结论罢（~~本质上还是简化统计前缀的方案数~~（大悲））

高级数据结构（一）

这个写一条写不完 /kk

关于 区间操作查询 啥的玩意（给定一堆操作，询问一段操作后的答案

有两种，询问之间独立的和不独立的

独立的可以用CDQ的思维来看，但大部分情况还是会感觉别扭

最好的还是找到修改之间的联系，正着看反着看咋看都行找到联系套来套去就可以AC（~~TLE~~）了

记得倍增大法/离线/卡常啊kora

关于水题（一）&关于比较乱x的题

~~读题啊啊啊~~

哭了水题又挂

总之感觉对于比较杂乱（不管是题面上的、变量上的、逻辑上的）还是要先理清思路罢，

对于这些维度、变量、描述特多的定死顺序有奇效

有的时候先去往某一定死的方向思考（或者说向着自己心中的灵感走）反而会出锅

~~读题啊啊啊~~

关于毒瘤题（一）

心态先稳住吧。。。关于这个我真的不是很有把握/kk

而不被题面吓到的精神想必是紧随其后的罢

不要没手没脚的乱来，推结论先

关于字符串（一）

现在脑子都麻了。。见到字符串题只会想半天SAM还想不出

这是纯粹字符串底力问题吧？

总之最近多去做做SA，基本的SAM操作都会了，SAM/PAM套个不可名状物啥的巨形毒瘤题还是比较少

关于计算几何

记得有凸壳/凸包/扫描线/闵可夫/辛普森，基本上就会拿计算几何打辅助了（？）

退火能别用就别用

还有记得闵可夫怎么写

关于BSGS

数论题经常都是离正解就差个BSGS。。。

为啥求离散对数的时候还记不得BSGS啊——

总之$a^x=b(\mod{c})$记清楚先啊

离散对数啊离散对数

说到这个分块的块大小记得要灵活点，均一波以防被系数背刺

关于组合题

经常伪装成奇怪的DP题

有些题还挺智商，往组合想还不好想

总之，~~警惕新型网络诈骗~~

复杂度的结论

有些不太记的住。。。

有些树形背包有$O(n^2)$做法

调和$log$

自然数约数个数和$log$

$d(n)$大约在$log$和$\sqrt{n}$之间

主定理

无向图中度数种数$O(\sqrt{m})$

高级数据结构（二）

二更

别忘了有主席树这种东西（主席树可以单点/区间修改，别忘OWO）

有些时候一些看似有关联的东西可以拆开求（如左右端点）

6.30

网络流

笑死，写了4个小时的缝合怪

最大流费用流倒是不虚（除了缩圈（捂脸）），主要还是上下界流的问题

其次就是网络流模型的运用

最后就是记得有网络流这个东西

没了？没了

记得最小割树啊QAQ

图论问题（一）

有点杂

先讲最短路

标准的最短路肯定没问题，，主要是优化啥的

记得倍增大法/二进制分组/线段树DS建图/对点数、边数的优化

还有就是对于点边数比较小的时候别忘了有Floyd

最后

奇怪的树形DP

DFS序上的，欧拉序上的

维护线段树的，维护集合的，~~维护凸壳的~~

记得最优解优化，往往$O(n^2)->均摊O(nlogn)$

还有DP优化的技巧（容易忘的那种）：单调性（打表），two-pointers

奇怪的数学题

给个长得很jb高考的函数让你干啥干啥

看着就恶心，你也不会做

但实际上慢慢推一下还是可做的

就是智商方面有待加强（（

7.1

数论和矩阵

递推式啥的需要化简或改变形式

技巧方面可以部分预处理平衡复杂度

线代相关。。底力问题，大概就是行列式矩阵的手工化简啥的

和数论函数复合的题手工化简有奇效

化简结果找找规律看能不能直接出或者化成卷积/反演的形式

感觉标准形式化不出来可以举例化简

老生常谈.jpg

something else

尽可能保持思维活跃吧

尽量不要觉得不太可做的样子

特别是推出奇怪的式子的时候，模型化能力要跟上

DP（一）

对于可能会卡在推式子的题，可以尝试运用反函数的思维

记得单调性

能三分甚至可以三分

字符串（二）

新思路，可以先考虑暴力DP啥的

顺便一提，DP优化不要忘了MeetInMiddle和四边形不等式

又被SAM骗了好气啊（）

关于图论模型

记得能建图论模型

就行了

7.2

一些看着很计数又很集合的题

优先考虑DP，先找顺序和不变量，依次列出式子、找到性质

如
$$
给定 S,C ，你需要计算有多少 (c,s) 满足 1≤c≤C,1≤s≤S 且存在一组边长均为正整数的矩形使得它们的周长之和为 c ，面积之和为 s 。
$$
这种题，就可以先看出$c/s$的最大值为$2$，然后设出$x=2s-c$用以标记顺序，且因此有了在集合中加入正方形$x$不变的性质，因此对于固定的$x$来说有$s_{min}$使得$s>=s_{min}$存在一合法解。这是构造顺序进行DP的过程。

然后列出关于$x$的DP式子。

然后由于题目有实际意义，可以打表观察法进行__转移点方面的优化__。

7.16

N2O5-A

看似很水的一道欺诈题，pollard-rho只有60分/kk（因为可能被卡）

实际上有前缀和思想的O(n^2)做法（把log均摊掉）

大概是不断地做G=gcd(G, Si)，i递减，S为前缀积

N2O5-B

定义好点为根当前当前点的最大值为当前点的权值的点，一棵树的权值定义为所有重标号方案的K的好点数次幂和。

求一棵树的权值，要求O(n^2)。

树形DP，做法有点小多

其中一种做法为从叶到根的合并式DP

首先考虑枚举每种好点/非好点的方案（针对树点），求出每种方案的总数（针对重标号）

可以发现一种方案对应一种偏序关系，可以在DP的过程中动态维护这种关系。而这样的关系具有特殊的结构特征：每个好点的子树内的点的偏序关系可以在该子树内有关（方法为重构有向树，即小的连向大的），而非好点的子树在除掉该子树内好点的子树后剩下的点构成连通块，且偏序关系未确定且只与祖先好点相关，这样的点定义为散点（在重构树上未定向的点），散点在根向DP时会在遇到好点时贡献，遇到非好点时继承

有了这样的散点的概念，就可以舍弃枚举方案的思想，直接记录散点数，即$DP[i][j]$为$i$点子树里所有情况的贡献之和（其实就是把枚举的方案通过散点这一性质合并了），贡献定义为与树大小相关的乘法，可以$O(n^2)$树形背包。

其次还有容斥的做法，但仍然是树形DP，相当于弱化为有向树确定偏序关系种数的模型（CTS2019D2T2），DP时叶向边直接贡献，根向边拆成__删除__和__反向__两种处理方法，对单个点做容斥，删除为正反向为补，容斥系数为-1，因而可以在DP过程中直接处理，这样做是$O(n)$。扩展到这道题时仍需在重构树上找性质，但可以沿用容斥的基本思想无假。

N2O5-C

生成函数多项式题，之后补。

N2O6-A

求$k*k(n<=k<=m)$，对角线为${a_i(i<=n),0(i>n)}$，其余元素为$1$的矩阵的积和式：$\sum_{p_i}\prod_{i} A_{i,p_i}$，$p_i$为排列

实际上很简单

先想$n*n$，枚举取到的对角线数的集合，并使用错排数：

$\sum_S W_{n-|S|}\prod_{i\in S}a_i$

$=\sum_{i=0}^{n}F_i W_{n-i}$

$F_i$为所有$|S|=i$的集合权值的和，所以目前的答案为上述多项式（卷积后）的第$n$项（题目要求的答案为$n$到$m$项）

因为$F_i=0(i>n)$，

所以只要求出$F$前$n$项，就可以求出所有的答案

因为$F$与集合大小相关，考虑分治做法，有$F^{l,r}=F^{l,mid}F^{mid+1,r}$， $$此处为卷积

$O(nlog^2n)$随便做

TIPS：走火入魔用成容斥就难做了。。

N2O6-B

给出数组（降序）和递推式子求值

考虑递推式的意义，不可以发现递推式求出的式子为原数组的哈夫曼树（合并石子），$O(nlogn)$裸爆

因为若设$i$为数组元素使用数，$j$为剩余叶子结点数（初始只有根节点），

$(i,j)->(i+i,j-1)$为把$i$值放到$j$处；

$(i,j)+suf_i->(i,2j)$为让剩下的叶子节点自己生两个儿子出来（叶子结点翻倍），顺便费用提前计算.

~~怎么想出来的？？~~

话说这种DP挺巧妙的

N2O6-C

趣事：听讲题的时候一直以为是$10^5$范围，突然发现讲到$O(n^2logn)$没讲了。。

题意为给定$n$个向量和2个点，求$n$个向量中最多$k$个向量之和确定的点与这两个点距离之和的最大值

因为等距点在椭圆上，而我们求的是最外层的点，所以根据与椭圆相切的原理，用线性规划的方法，存在$k$，使得在最大化$z=ax+by$，$(x,y)$取A点构成的凸包时取到最优的点

因此暴力做法就是枚举斜率和符号（记得特判$\alpha = \pi/2$），确定前$k$个点（通过$ax+by$降序排列）

但很明显$ax+by$不重要，重要的是向量之间的偏序关系

我们可以对于每__对__向量求出他们之间的偏序关系变化的阈值，把这$O(n^2)$对阈值排序并依次swap向量的排序，每次在数组的前$k$项使用二分（排除贡献为负的项），时间复杂度为$O(n^2logn)$

7.17

N2O9-A

求除了(n,1)以外的上三角稀疏矩阵的行列式q次，每次求都要使k（最多20）个位置变成0，询问之间独立。

第一档：暴力高斯消元

第二档：稀疏矩阵且只对最后一行作用，高斯消元可以O(m)做，最终O(mq)

第三档（k=1）：用伴随矩阵$AA^*=|A|I$的性质乱杀，O(m+q)

正解：

把矩阵转化成图，问题缩减为求出1->n的路径权值和（1->n的路径要求递增，权值为$(-1)^{不在路径内的点数+1}\prod w_{路径内的边}$）

于是乎我们可以把$k$条限制边连接的点提出来构成一个新表，表中$A_{i,j}=i\rightarrow j的权值和(i<j,\bold {<i,j>}不是限制边),A_{i,j}=0(\bold{<i,j>}为限制边)$，做容斥，系数为-1，因此可以按点顺序遍历做到$O(k^2)$

其中i->j的权值和可以在询问前做到$O(nm)$的预处理

总复杂度$O(nm+qk^2)$

ABC210E

智商题，注意奇怪的数论技巧，无从下手就手玩一下

ABC210F

2-SAT，看得出来就挺经典了

注意到n大约为5e4水平，大概就是要拆成约数/质因数

那么最基本的定义就蛮简单：$A_{p,i}=拥有质因子p的第i个数被选了,A_{p,i}\rightarrow 非A_{p,j}(j!=i)$

同时为每个数建立一个总点，分点向总点连边，总点向分点连边，总点与其对应的数的反命题总点连边

但是这样边数就是$O(n^2log^2n)$，受不住

于是就可以经典地定义前后缀或，$S_{p,i},T_{p,i}$表示前/后缀内是否有为正的命题

所以$S_{p,i}\rightarrow S_{p,i+1},S_{p,i}\rightarrow 非T_{p,i+1},非S_{p,i}\rightarrow非S_{p,i-1},非S_{p,i}\rightarrow T_{p,i+1}$

$T_{p,i}$同理

边数降至$O(nlogn)$

记得标准的2-SAT只要任意强联通分量内没有矛盾就是yes

7.18

N2O9-B

直接分析

在一个SCC内，周期等于gcd(环长)

证明：从一个点出发进行$gcd$色染色，可以发现染色过程即为该点在图上运动的过程，每个时刻该点占据的点的颜色不断闪烁，周期就是gcd.

在一个图内周期等于lca(SCC的周期)

证明：对于所有$i$有$d_i|D$，即$D$为lca.

思考怎么求SCC内所有环长的gcd

因为我们关注的是gcd而非环长本身，我们可以尝试运用辗转相减/除等技巧

我们发现返祖边能形成一个大小可求的环

横叉边能是某一些环的长度加减某个可求的值

于是上述说的所有数据做gcd即为所求

求循环开始处可以倍增矩阵幂解决（~~倍增和二分相比，那我觉得~~）

N2O9-C

首先列出方程，发现系数很范德蒙德行列式，于是考虑用Cramer法则求解

尝试把向量$B$放在向量组${A_n}$的末尾，列出式子$D=\prod_{i=0,j<i}^{n}(a_i-a_j)$

则$x_i=\frac{\frac{D}{\prod_{j!=n}(a_n-a_j)}}{-\frac{D}{\prod_{j!=i}(a_i-a_j)}}=-\frac{\prod_{j!=i}(a_i-a_j)}{\prod_{j!=n}(a_n-a_j)}$

分母可以直接求，分子设为$D_i=\prod_{j!=i}(a_i-a_j)$

直接运用快速插值的柿子就行了，但，推导：

有点像拉格朗日插值的柿子，考虑设一个可以消去无关项影响的多项式函数，则可以设$F(x)=\sum_{i=0}^{n}\prod_{j=0,j!=i}^{n}(x-a_j)$

则$D_i=F(a_i)$

通过观察（智商经验 ~~洛必达~~ 快速插值）发现$F(x)=\frac{d(\prod_{j=0}^{n}(x-a_i))}{dx}$

然后套裸的多点求值就行了（~~常数变成了一道光~~）

多项式

复习一下

FFT（扶扶她）

inline void FFT(C *c, int inv) {
	for(R i = 0; i < N; i++) if(i < r[i]) swap(c[i], c[r[i]]);
	for(R mid = 1; mid < N; mid *= 2) {
		C tmp(cos(pi / mid), inv * sin(pi / mid));
		for(R i = 0; i < N; i += mid * 2) {
			C om(1, 0);
			for(R j = 0; j < mid; j++, om = om * tmp) {
				C x = c[i + j], y = c[i + j + mid] * om;
				c[i + j] = x + y, c[i + j + mid] = x - y;
			}
		}
	}
    if(inv == -1) for(R i = 0; i < N; i++) c[i].r = c[i].r / N + 0.5;
}

inline void FFT(C *c, int inv) {
    for(R i = 1; i < N; i++) if(r[i] > i) swap(c[i], c[r[i]]);
    for(R mid = 1; mid < N; mid <<= 1) {
        if(inv == 1) for(R i = 0; i < mid; i++) w[i] = pw[N / mid * i];
        else for(R i = 0; i < mid; i++) w[i] = iw[N / mid * i];
        for(R i = 0; i < N; i += (mid << 1)) {
            for(R j = 0; j < mid; j++) {
                C x = c[i + j], y = c[i + j + mid] * w[j];
                c[i + j] = x + y; c[i + j + mid] = x - y;
            }
        }
    }
    if(inv == -1) for(R i = 0; i < N; i++) c[i].r = c[i].r / N + 0.5;
}

后者加了单位根的常数优化

单位根为$w_{i}^{j}=(jcos(\frac{2\pi}{i}),jsin(\frac{2\pi}{i}))$

${w_{i}^{j}}^{-1}=(jcos(\frac{2\pi}{i}),-jsin(\frac{2\pi}{i}))$

NTT（脑瘫瘫）

inline void ntt(int *c, int inv) {
    for(R i = 1; i < N; i++) if(r[i] > i) swap(c[r[i]], c[i]);
    for(R mid = 1; mid < N; mid <<= 1) {
        int w = ksm(g, (mod - 1) / (mid << 1));
        if(inv == -1) w = ksm(w, mod - 2);
        for(R i = 0; i < N; i += (mid << 1)) {
            int o = 1;
            for(R j = 0; j < mid; j++, o = 1LL * o * w % mod) {
                int x = c[j + i], y = 1LL * o * c[j + i + mid] % mod;
                c[i + j] = (x + y) % mod; c[i + j + mid] = (x - y + mod) % mod;
            }
        }
    }
    if(inv == -1) {
        int w = ksm(N, mod - 2);
        for(R i = 0; i < N; i++) c[i] = 1LL * w * c[i] % mod;
    }
}

单位根$w_i^j=g^{\frac{M-1}{i}}$

${w_i^j}^{-1}$可以直接快速幂算

同样可以对单位根常数优化

分治FFT

实际上是CDQ，每层把左边的贡献附加到右边.

可以被多项式求逆替代，挺那啥的.

多项式求逆求解分治FFT：$F(x)=F(0)*(1-G(x))^{-1}$

多项式求逆&多项式开根&多项式除法&多项式取模

阅读这个博客.

柿子：

多项式求逆：$B(x)=G(x)*(2-A(x)*G(x))$

多项式开根：$B(x)=\frac{G(x)}{2}+\frac{A(x)}{2G(x)}$

多项式除法：$rev(D(x))\equiv rev(A(x))*rev(B(x))^{-1}(mod\ x^{n-m+1})$

多项式取模：$rev(R(x))=rev(A(x))-rev(B(x))*rev(D(x))$

全是$O(nlogn)$

多项式多点求值

分治+多项式取模，每次取模都可以划分为模数多项式的子问题$O(nlog^2n)$

具体讲讲吧

设你要求的值为$a_i$，生成多项式$B_{l,r}(x)=\prod_{i=l}^r(x-a_i)$

那么让$F(x)=B_{l,mid}(x)D(x)+R_L(x),F(x)=B_{mid+1,r}(x)D(x)+R_R(x)$，则$F(a_i)=R_L(a_i)$

常数巨大，使用前记得祈祷

快速（龟速）插值

先对拉格朗日插值的分母经过$N2O9-C$里的推导后应用多点求值

然后分治FFT/多项式求逆直接解出来，$O(nlog^2n)$

常数巨大，使用前请务必祈祷

7.19

N2O7-A

贪心做，忽略ci后每只青蛙都没有区别，所以预处理出最多有多少只青蛙能免费渡河，这里可以贪心地往选择右边选择石头

A.有d(>0)只，因为没有用到石头可以加入任意一只免费青蛙的路径里，所以出去免费青蛙都可以以一次代价渡河，排序解决

B.一只都没有，最优情况是让ci最小的青蛙遍历全部石头，其他青蛙一次跳过

N207-B

首先如果取出3种字母，则答案下界可降低至$\frac{n^2}{9}$

然后尝试搜索长度小于9的所有循环节，尝试上下界剪枝，设当前循环节长度为$k$，取出的序列长度为$m$，某一种数字使用的个数为$j$，则答案为$\frac{m^2}{k}$，而取出该种数字组成的序列答案下界为$\frac{m^2j^2}{k^2}$，相除结果为$\frac{k}{j^2}$，$k$最大值为8，所以在$j\geq 3$时可以减掉，搜索的复杂度因此变得异常地小.

N2O7-C

观察题目，推导出以下性质：

由于B插入A的位置可以随意选择，且A每次删除的模式只与值域有关，故不考虑B中元素时A中元素递增$\Longleftrightarrow$考虑B中元素时A中元素递增
由于A每次删除的模式只与值域有关，故A中元素在值域轴上连续
若选择的值域$E\subset F$，则$F$的答案必不劣于$E$。证明：假设$E+{x}=F$，即$E$与$F$只差一个元素，则为清除$x$必须为其安排一个操作。由于奇偶操作有异，则该操作有可能全新，有可能选择一个空操作代替，但不可能减少操作的次数

这样就可以每次在A的值域上选择极长连续子段（$w[val[i]]=i$）进行模拟，$O(n+m)$

数论复习（上）

从最基础来

辗转相除法

1
2
3

void gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

辗转相减法

主要与数位相关的技巧（如高精度）、线性组合有关

同余

自反性、对称性、传递性

$a\equiv b(mod\ m),c\equiv d(mod\ m)\longrightarrow a+b\equiv c+d(mod\ m)$

$a\equiv b(mod\ m),c\equiv d(mod\ m)\longrightarrow ab\equiv cd(mod\ m)$

$a\equiv b(mod\ m)\longrightarrow ak\equiv bk(mod\ mk)$

$a\equiv b(mod\ m),d|gcd(a,b,m)\longrightarrow a/d\equiv b/d(mod\ m/d)$

$a\equiv b(mod\ m),d|m\longrightarrow a\equiv b(mod\ d)$

$a\equiv b(mod\ m)\longrightarrow gcd(a,m)=gcd(b,m)$

裴蜀定理

对于方程$ax+by=c$，方程有解 $\Longleftrightarrow gcd(a,b)|c$

乘法逆元

$a*a^{-1}=1(mod\ m)$，则称$a^{-1}$为$a$在$mod\ m$下的乘法逆元

$a$有乘法逆元的充要条件为$a\perp m$

欧拉定理

$a\perp m\longrightarrow a^{\phi(m)}\equiv 1(mod\ m)$

$\phi(m)$是欧拉函数

费马小定理是其特殊形式

扩展欧几里得算法

求解方程$ax+by=gcd(a,b)$

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

$x=y’,y=x’-\lfloor \frac{a}{b}\rfloor y’$

求出来的解必然有$|x|\leq b,$

通解为$x=x_0+k\frac{b}{gcd(a,b)},y=y_0-k\frac{a}{gcd(a,b)}$

中国剩余定理（拉格朗日插值）

求解线性同余方程组$x=a_i(mod\ m_i)$，要求$m_i$两两互质

设$M=\prod m_i,M_i=\prod_{j\neq i}m_j,b_i\equiv M_i(mod\ m_i)$

则$x\equiv \sum_{i=1}^{n}a_iM_ib_i(mod\ M)$

扩展中国剩余定理

用扩展欧几里得合并方程：

$x=x_1+k_1m_1,x=x_2+k_2m_2$

$k_1m_1-k_2m_2=x_2-x_1$

… …

$x\equiv k_1*m_1+x_1(mod\ lca(m_1,m_2))$

阶

$a^n\equiv 1(mod\ m)$中，若$n$取最小，则$a\ mod\ m$的阶为$\delta_m(a)=n$

$1,a,a^2,…,a^{\delta_m(a)-1}$不同余

若$a^p\equiv a^q(mod\ m)$，则$p\equiv q(mod\ \delta_m(a))$

若$a\perp m,b\perp m$，则$\delta_m(ab)=\delta_m(a)\delta_m(b)\Longleftrightarrow gcd(\delta_m(a),\delta_m(b))=1$

$\delta_m(a^k)=\frac{\delta_m(a)}{gcd(\delta_m(a),k)}$

原根

若$gcd(a,m)=1,\delta_m(a)=\phi(m)$，则$a$为$m$原根

判定：$g^{\phi(m)/p}!\equiv 1(mod\ m)$，$p$为$\phi(m)$的因数（不为0或其自身）

原根有$\phi(\phi(m))$个，只有在$m=2,4,p^\alpha,2p^\alpha$有原根

最小原根是$O(n^{\frac{1}{4}})$的，所以可以暴力求原根

BSGS

求$a^x\equiv b(mod\ m),a\perp m$（离散对数），转化为$a^{A\sqrt{m}}\equiv ba^B(mod\ m)$.

求$x^a\equiv b(mod\ m),m有原根$，设$x=g^c$，则转化为$g^{ac}\equiv b(mod\ m)$，即求离散对数.

求$a^x\equiv b(mod\ m)$，当且仅当$gcd(a^{\inf},m)|b$时方程有解

让方程变成$\frac{a^k}{D}a^{x-k}\equiv \frac{b}{D}(mod\ \frac{m}{D})$

变成$a^{x-k}\equiv \frac{b}{D}(\frac{a^k}{D})^{-1}(mod\ \frac{m}{D})$

就可以解了

米勒·拉宾

inline bool mr(ll x, ll y) {
	ll k = x - 1;
	while(k) {
		ll cur = qpow(y, k, x);
		if(cur != 1 && cur != x - 1) return 0;
		if(k & 1 || cur == x - 1) return 1;
		k >>= 1;
	}
	return 1;
}

inline bool isp(ll x) {
	if(x == 46856248255981LL || x < 2) return 0;
	if(x == 2 || x == 3 || x == 7 || x == 61 || x == 24251) return 1;
	return mr(x, 2) && mr(x, 3) && mr(x, 7) && mr(x, 61) && mr(x, 24251);
}

玄学算法，背他就完了

泼辣的·肉


inline ll func(ll x, ll c, ll m) {
	return (smul(x, x, m) + c) % m;
}

inline ll pr(ll x) {
	ll s = 0;
	ll t = 0;
	ll c = rand() % (x - 1) + 1;
	ll val = 1;
	ll goal = 1;
	while(1) {
		ll d;
		FOR(step, 1, goal) {
			t = func(t, c, x);
			val = smul(val, aBS(t - s), x);
			if(step % 127 == 0) {
				if((d = gcd(val, x)) > 1) return d;
			}
		}
		if((d = gcd(val, x)) > 1) return d;
		goal <<= 1;
		s = t;
		val = 1;	//val要重置
	}
	return 114514;
}

7.20

N2O8-B

考虑对边分析贡献

发现对于两个相邻空白行来说，其间的边只能经历$up*down$次（因为限制点很稀疏，所以可以思考缩点做法）

于是累计两行贡献，同时把两行合并（相当于边权赋0）

发现把行合并完以后，可以对列合并

最后的图是$O(n^2)$，又由于边权都是1（即还是网格图，点权变了），所以可以$O(n^4)$bfs.

N2O8-C

你会发现一个点使用B边和R边的数量可以互相表示

于是可设出n-1个未知数

于是可以根据度数列出方程$Ax=B$

你会发现$A$是不变的，输入的字符串只改变$B$中的常数，所以可以用矩阵求逆的方法求解线性方程组，$O(n^3+qn^2)$

判无解：显然，所有经过的点必然最终通往输入点$v$，因此所有用过的点最后使用的出边连成的图是$v$的根向树是有解的必要条件（至少最后一次离开的出边一定直接地通往$v$）

假设已经构造出了一个根向树，那么任何不论你在任何一个点，当前开放的是条边，你都可以走到一个最终一定会通往$v$的点，因此根向树是有解的充分条件

数论复习（下）

数论函数板块

积性函数

满足$F(pq)=F(p)F(q),p\perp q$

$\epsilon(n)=[n=1]$

$I(n)=1$

$Id(n)=n$

$d(n)=\sigma_0(n)=\sum_{d|n}1$

$\sigma(n)=\sigma_1(n)=\sum_{d|n}d$

$\phi(n)=\sum_{i<n}[i\perp n]$

$\mu(n)={1(n=p_1p_2p_3…p_k,2|k),-1(n=p_1p_2p_3…p_k,2\perp k),0(otherwise)}$

积性函数与积性函数的狄利克雷卷积是积性函数

狄利克雷卷积

$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

$\mu*I=\epsilon$

$\phi*I=Id$

$\mu*Id=\phi$

莫比乌斯反演

$\sum_{d|n}\mu(d)=[n=1]$，即$\mu*I=\epsilon$，基本式

$g(n)=\sum_{d|n}f(d)\Longleftrightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$

$g(n)=\sum_{n|d}f(d)\Longleftrightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)$

线性筛

没啥好讲的，记得$\phi(1)=\mu(1)=1$以及它们怎么推

数论分块

别忘就行，记得可以嵌套，记得可以前缀和

杜教筛

$O(n^{\frac{2}{3}})$求积性函数单点前缀和

$S_f(n)g(1)=S_h(n)-\sum_{i=2}^nS_f(\lfloor \frac{n}{i}\rfloor)g(i)$

其中$f*g=h$

要加以整除分块和合理的记忆化

burnside引理/polya定理

$t=\frac{1}{|G|}\sum_{i=1}^{s}c_1(g_i)$

一个置换群把数字分为等价类的个数为所有置换不动点数的算数平均数

$t=\frac{1}{|A|}\sum_{i=1}^{s}m^{c(a_i)}$，$c(a_i)$表示置换$a_i$的循环数

一个简单的染色问题中方案数为颜色数的所有置换循环数次方的平均数

burnside是对情况的置换，polya是对染色的置换

7.21

N2O10-A

我们尝试优化暴力：枚举诱导子图，如果连通块数为1，答案更新，否则忽略

也就是求：$\sum_{S\subset V}x^{c(S)}(mod\ x^2)$

一般地，可以令$x=2$

于是问题转化为对图黑白灰染色，要求黑色只与白/灰相连，白色只与黑/灰相连

也就是对诱导子图里的连通块黑白染色的结果

直接DP$O(3^{13}n)$

N2O10-B

鸽，听不懂

N2O10-C

鸽，还没听

7.22

数据结构复习

这个没啥好写的。。。

线段树&树状数组

没啥

平衡树

Splay：写过了，手感很好

FHQtreap：好些，能可持久化，性价比比较高（？）

记得文艺操作啥的东西

树套树

线段树套平衡树：没啥好讲的，莽就完了

二维线段树：$O(n^2logn)$，拉

树状数组套主席树：相对来说比较好想，都是前缀和嘛

kdt

很特别的一种数据结构

记得怎么用：维度轮流划分，nth_element，估价函数（到矩形的最大/最小距离），根据估价函数暴力回溯搜索

CDQ

思路是用左边的来贡献右边的

通常思考方法是列出题目中进行贡献的不等式组，依照不等式组的个数套CDQ

一个CDQ的做法是对第一维分治，对第二维排序，对第三维计算贡献

多个CDQ可以把前几维重标号为0/1，最后统计贡献的时候只计算(0,0,0…)对(1,1,1…)的贡献

整体二分

不怎么会/kk

答案要有可二分性

修改要相互独立

同时对所有的询问进行二分，在二分区间的同时把询问根据需要分到不同的子区间中

这是最基础的，高级的运用不会了

虚树

很简单

记住：栈内元素是一条链，栈内元素没有连边，出栈的时候才连边，用DFN排序

树链剖分

轻重链剖分：简单且常用

长链剖分：对付关于深度的DP的宝具。对一个点而言，其能继承其长儿子的DP数组，要动态开数组（其实vector也行）

点分治/点分树

记得，能用，就行

字符串

这个早点复习好

kmp（看*片）

处理next[i]数组，border

Z算法（扩展kmp）

不怎么会，爬了

AC自动机

自动机

原图是一个trie，加入了能够处理失配情况的fail[i]数组，原理是连向极长后缀，可能根据上一个前缀的状态推出

inline void build() {
	head = 1, tail = 0;
	FOR(i, 0, 25) {
		if(tr[0][i]) q[++tail] = tr[0][i];
	}
	while(tail >= head) {
		int u = q[head++];
		FOR(i, 0, 25) {
			if(tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q[++tail] = tr[u][i];
			else tr[u][i] = tr[fail[u]][i];
		}
	}
	FOR(i, 1, tc) {
		g[fail[i]].push_back(i);
	}
}

大概就是这样，记得第一层特殊处理，在向外更新时处理fail[i]数组

SA

inline bool cmp(int x, int y, int w) {
	return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

FOR(i, 1, n) cnt[rk[i] = s[i]]++;			//A基数排序
FOR(i, 1, m) cnt[i] += cnt[i - 1];			//A基数排序
DEC(i, n, 1) sa[cnt[rk[i]]--] = i;			//A基数排序（初始化，以ascii码为关键字）
for(int w = 1, p; w < n; w *= 2, m = p) {
	p = 0;									//B预处理第二维信息
	FOR(i, n - w + 1, n) se[++p] = i;		//B预处理第二维信息（根据第二维将后缀排序）
	FOR(i, 1, n) {							//B预处理第二维信息
		if(sa[i] > w) se[++p] = sa[i] - w;	//B预处理第二维信息（枚举第二维反过来加入后缀）
	}
	memset(cnt, 0, sizeof(cnt));			//C基数排序
	FOR(i, 1, n) cnt[fi[i] = rk[se[i]]]++;	//C基数排序（关键字是第一维，顺便把第二维和第一维对应一下）
	FOR(i, 1, m) cnt[i] += cnt[i - 1];		//C基数排序
	DEC(i, n, 1) sa[cnt[fi[i]]--] = se[i];	//C基数排序（按第二位顺序安置答案）
	memcpy(oldrk, rk, sizeof(rk));						//D更新排名数组（作用是在基排中链接两个维度）
	p = 0;												//D更新排名数组
	FOR(i, 1, n) {										//D更新排名数组
		rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;	//D更新排名数组（判断相邻的后缀是否相同）
	}
    if (p == n) {
    	for (int i = 1; i <= n; ++i) sa[rk[i]] = i;		//E判断break
    	break;
    }
}

height数组：

$height[i]=lca(sa[i],sa[i-1])$，第$i$名和第$i-1$名

有$height[rk[i]]\geq height[rk[i-1]]-1$，第$i$处和第$i-1$处

于是可以$O(n)$预处理

for (i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    h[rk[i]] = k;
}

应用：

寻找最小循环位移。把字符串复制一遍跑。
在线寻找子串。在后缀数组上二分，比较后缀和模式串的字典序大小。因为模式串的出现在SA里是连续的，所以可以二分出上下界得到匹配数。
首尾取字符最小化字典序。把字符串镜像地复制一遍变成回文串，每次选择的时候比较正向和反向的大小，于是可以贪心地选择。
子串最长公共前缀。运用height数组$lcp(sa[i],sa[j])=min{height[i+1…j]}$，变成RMQ力。
比较子串大小。把两个子串对应的后缀求出lcp后比较。
求子串数。分别对每个后缀统计前缀，并减去重复。
子串出现$x$次$\Longleftrightarrow$有连续$k$个后缀以该串为前缀。
不重叠的相同子串$\Longleftrightarrow$在lcp相同的段内&$\Delta$原串下标$\geq$串长
结合数据结构，即按照顺序组织数据，可以以$sa[i],rk[i],height[i]$为维度/数据

SAM

inline void ins(int v) {
	int k = ++sc, p = las;
	sam[k].len = sam[p].len + 1;
	siz[k] = 1;
	for(; p && !sam[p].tr[v]; p = sam[p].fa) sam[p].tr[v] = k;//把上一个位置及其祖先更新
	//printf("^%d\n", p);
	if(!p) sam[k].fa = 1;//没有一个祖先有相同字母的边，link直接连向1
	else {
		int q = sam[p].tr[v];
		if(sam[q].len == sam[p].len + 1) sam[k].fa = q;//找到的这个祖先加上这个字母就是一个以它为maxlen的等价类，所以该等价类包含k
		else {//找到的这个祖先加上字母是一个等价类的非maxlen，k和它不成包含关系
			int w = ++sc;
			sam[w] = sam[q];
			sam[w].len = sam[p].len + 1;//建一个lca等价类
			sam[k].fa = sam[q].fa = w;
			for(; p && sam[p].tr[v] == q; p = sam[p].fa) sam[p].tr[v] = w;//q不再包含原先的部分endpos转移到了w里，连向q的重定向至w
		}
	}
	las = k;
}

应用：

模式匹配。
不同子串个数/长度和。涉及到不同的子串都可以思考SAM。可以在DAG用路径来DP，也可以在link树上统计等价类的答案。
比较子串字典序的大小。字典序可以通过DAG中路径的权值体现
最小循环位移。基本原理：找子串。把字符串复制一遍寻找最小的|S|串。
1. 模式匹配求出现次数。涉及到预处理endpos集合的问题。由原串前缀创建的等价类endpos大小初始为1，虚拟lca节点大小初始为0。在link树上做一个子树和就行。
模式匹配求第一个匹配位置。涉及到预处理firstpos（endpos中的最小值）的问题。预处理时字符串前缀点初始值为$len(k)$，新建lca节点时初始值可以为$firstpos[q]$（也可以为0，无所谓），最后做个子树最小值。
最长公共子串。建立S的SAM，对于T依次加点，即在S中找T的每个前缀的最大后缀。每次用前一个状态来匹配当前字符，如果有匹配边则状态++，没有就跳link，即是不断找当前匹配处的前缀。
最长公共子串。建立伪广义后缀自动机，对每个状态状压一个endpos里有哪些原串。找到len最大的满状压的状态。

7.23

图论复习

最短路

dijkstra，SPFA，floyd

强联通分量/缩点

tarjan：

inline void tar(int u) {
	low[u] = dfn[u] = ++dc;
	sta[++top] = u;
	vis[u] = 1;
	VEC(i, g[u]) {
		int v = g[u][i];
		if(!dfn[v]) tar(v), low[u] = min(low[u], low[v]);
		else if(vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]) {
		while(top) {
			int v = sta[top--];
			col[v] = u;
			vis[v] = 0;
			if(v == u) break;
			a[u] += a[v];
		}
	}
}

强联通分量必有环

割点/点双联通分量

void tar(int u, int fa) {
	int cnt = 0;
	low[u] = dfn[u] = ++dc;
	VEC(i, g[u]) {
		int v = g[u][i];
		if(v == fa) continue;
		if(!dfn[v]) {
			cnt++;
			tar(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u] && fa) cut[u] = 1;
		}else low[u] = min(low[u], dfn[v]);
	}
	if(cnt >= 2 && !fa) cut[u] = 1;
}

一个点可以在多个点双内

仙人掌：每条边最多在一个环上的图

圆方树：对于仙人掌上的一个环建一个方点连向环上的所有圆点

广义圆方树：将普通图按点分划分，每个点分建方点连向点分内的所有圆点

广义圆方树建法：

void tar(int u, int fa) {
	low[u] = dfn[u] = ++dc;
    入栈;
	VEC(i, g[u]) {
		int v = g[u][i];
		if(v == fa) continue;
		if(!dfn[v]) {
			tar(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
                出栈直到v;
            }
		}else low[u] = min(low[u], dfn[v]);
	}
}

桥/边双联通分量

void tar(int u, int fa) {
	low[u] = dfn[u] = ++dc;
	VEC(i, g[u]) {
		int v = g[u][i];
		if(v == fa) continue;
		if(!dfn[v]) {
			cnt++;
			tar(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u]) [<u,v>是桥];
		}else low[u] = min(low[u], dfn[v]);
	}
}

和求割点很像

差分约束系统

求差分最大值：$x-y\leq k$，$y\longrightarrow x$，求最短路

求差分最小值：$x-y\geq k$，$y\longrightarrow x$，求最长路

2-SAT

处理好条件关系就行了

考虑完所有充分条件后多思考下是否必要

记得tarjan求强联通分量判有解的做法，只要SCC内有解就好

N1O1-A

转换：极长子段数=序列长-相邻两个灯都开着的个数

考虑到题目给出的数据不好维护，思考分块做法：对于总长度>B的颜色，动态维护；对于总长度<=B的长度，暴力更新。于是可以动态维护总长>B的颜色相邻的1的个数，每次暴力更新总长<=B的颜色的答案，并对前者贡献。

N1O2-B

设$x_i$为第$i$行处于的时间，则有$x_i-x_j\equiv k(mod\ T)$，则连$i\longrightarrow j:k$，易知周期为最小环的长度。

把矩阵横过来看设$y_i$为第$i$个灯由红转绿的时间，用同样的方法可以求出周期。

在建图后如果只连接相邻权值的边，则可以证明每一个简单环的长度都是周期。

（没怎么看懂，后补）

7.24

塔诺西的NOI day-x，咕咕咕

7.25

N102-A

实际上每个建筑的坚持时间$t_i=y_i+z_i$，$z_i$表示i在安全区内的时间。$x-z$图可表示为$(L,0),(M,R-L),(R,0)$

我们设有两个不同的M，$M_1,M_2$，分析它们的左边，发现任选两个$x$处的两个直线的差值$\Delta z$，有$x_1<x_2\Longleftrightarrow \Delta z_1 < \Delta z_2$，所以只要在某个M时有$y_i+z_i>y_j+z_j,x_i<x_j$，则往右的每个时间都有这个式子成立。于是可以把遍历所有$M=x_i$，预处理出它们的答案，然后左右一比对就行了（未完）

7.28

deleted

7.30

多项式&生成函数

FFT&NTT

讲完了

分治FFT

①分治做FFT

②分治FFT

生成函数

形式幂级数

只关心多项式系数，不关心x的取值

需要时x取任意值

如$0 < x < 1,1+x+x^2…=\frac{1}{1-x}$，且右麦克劳林展开后为左

$f(x)=1+x^3+x^6+x^9…=\frac{1}{1-x^3}$

$f(x)=1+2x+4x^2+8x^3=\frac{1-16x^4}{1-2x}$

$f(x)=1+2x+3x^2+4x^3…$

$\Longrightarrow f(x)=x(f(x)+\frac{1}{1-x})+1$

$\Longrightarrow (1-x)f(x)=\frac{1}{1-x}$

$\Longrightarrow f(x)=(\frac{1}{1-x})^2=(1+x+x^2…)^2$

指数生成函数(EGF)

两个EGF卷积能卷出一个组合数，相当于to_permutation

PGF

$F(x)=\sum_{i=0}{P(X=i)x^i}$

$F(1)=\sum_{i=0}{P(X=i)}=1$

$F’(1)=\sum_{i=0}{P(X=i)i}=E(X)$

把期望化成了多项式，便于推导和计算

FMT

求$c_i=\sum_{j&k=i}a_jb_k$

对$a,b,c$做一个高位后缀和（把$(i)_2$的位看成维，所有超集的和（不能容斥））得到$a’,b’,c’$，脑补一下可得$c’_i=a’_ib’_i$（显然）

然后对$c’_i$做个差分就行了

可扩展到k进制

FWT

或：$FWT(A)=(FWT(A_0),FWT(A_0+A_1)),IFWT(A)=(IFWT(A_0))$

子集卷积

合并子集的转移：$c_i=\sum_{j|k=i,j&k=0}{a_jb_k}$

占位多项式$\sum{a_ix^{popcnt(i)}}$

把popcnt相同的合并

CF1034E

发现对$c_ix^j$，$popcnt(i)<=j$，那么就可以直接令$x=4$，直接做OR卷积，最后每一项除以$4^i$，有贡献的$x^{j-i}$都为$1$.

HDU5823

斯特林数

第一类斯特林数

圆排列

$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$

$s(n,k)=\sum_{i=1}^nC(n-1,i-1)(i-1)!s(n-i,k-1)$

$G_n(x)=xG_{n-1}(x)+(n-1)G_{n-1}(x)$，生成函数求一行/列

第二类斯特林数

无区分集合

$S(n,k)=S(n-1,k-1)+kS(n-1,k)$

$S(n,k)=\sum_{i=1}^nC(n-1,i-1)S(n-i,k-1)$

$m^n=\sum_{i=0}^mC(m,i)i!S(n,i),n\leq m$

二项式反演：$S(m,n)n!=\sum_{i=0}^n(-1)^{n-i}C(n,i)i^m$

$S(m,n)=\sum_{i=0}^n\frac{(-1)^i}{i!}\frac{(n-i)^m}{(n-i)!}$

反转公式$\sum_{i=m}^nS(n,i)s(i,m)(-1)^{i-m}=[m=n]$

$\sum_{i=m}^ns(n,i)S(i,m)(-1)^{i-m}=[m=n]$

斯特林反演$f(n)=\sum_{k=0}^nS(n,k)g(k)\Longleftrightarrow g(n) = \sum_{k=0}^n(-1)^{n-k}s(n,k)f(k)$

HDU4372（todo）

考虑最大值在x，则x左边的每个最大值和右边的一堆数形成圆排列

Crash 的文明世界（todo）

把自然数幂化成第二类斯特林数

直接转化成$\sum_{i=0}^{m}S(m,i)i!\sum{C(n,i)}$

相当求右边

组合意义是从任意路径中选取i条边的种数之和

可以在树上DP

CF961G

对于每个下标列出式子$\sum_iw_i\sum_{j=1}^nC(n-1,j-1)jS(n-j,k-1)$

右边的式子化简$\sum_{j=1}^{n}C(n-1.j-1)S(n-j,k-1)+\sum_{j=1}^n$

2018雅礼方阵

只对行进行限制：$g(m)=(c^m)^{\underline{n}}$

两种限制同时进行：$f(m)$，有$g(m)=\sum_{i=0}^{m}S(m,i)f(i)$，（枚举等价的列）

然后反演：$f(m)=\sum_{i=0}^{m}(-1)^{m-i}s(m,i)g(i)$

ZJOJ2018 历史

NOI2021E（todo）

首先明显可以看出是矩阵和平衡树的题

现在的问题是如何处理W和E两种操作和生成序列

首先先让分子分母不翻转，每次按照奇偶性修改分子/分母

发现W可以化成加入0 1

E不论最后一个数是否为1，都可以令最后一个数–，然后加入1 1；即加入0 -1 1 1

然后可以构造矩阵塞进平衡树

所以每个点维护4个矩阵：WE反转/不反转，WE翻转/不翻转

NOI2021D（todo）

把字符串分成k+1（16）段，鸽笼原理，有可能正确的字符串必有一段和输入匹配

分组，哈希，玄学

NOI2021B（done）

偶数和奇数的乘法与1和-1的乘法是相似的

每2个交点不改变对答案的贡献，所以从第一层直接连到第n层的交点的奇偶性就是其所有路径的奇偶性

NOI2021C（todo）

缩点，重构，虚树

牛顿迭代法求逆元

用于求$mod\ p^k$意义下的逆元

类似于多项式求逆/开根

$xA\equiv 1(mod\ p^k)$

$xB\equiv 1(mod\ p^{2k})$

$(B-A)^2\equiv 0(mod\ p^{2k})$

$B^2-2AB+A^2\equiv 0(mod\ p^{2k})$

$B\equiv A(2-Ax)(mod\ p^{2k})$

[数论]例题1

$C(n,i)=\frac{n^{\underline{i}}}{i!}$，预处理逆元直接递推

[数论]例题2

只要区间里有质数，就是正解

小区间直接搜

欧拉定理推广

$a^b\equiv a^{min(b\ mod\ \phi(m) + \phi(m), b)}(mod\ m)$

[数论]BZOJ3884

求$2^{2^{2^{…}}}\equiv x(mod\ p)$

相当于求$左\equiv x’(mod\ \phi(p))$

7.31

群论

陪集分解轨道稳定集定理

CF1508D（done）

对于单独的一个环，可以找到一个根节点做一个菊花

对于多个环，可以尝试交换点，合并成一个大环

按照极角排序，每次交换只交换极角相邻的点，可以保证有解

CF1442D（done）

最多只有一个数组没有选满

考虑分治，递归选择没选满的数组，则每次往下走都把另一边的数组背包合并，最后找到的那个位置就枚举前缀

AGC046D（done）

设$dp[i][j][k]$为删到了$i$处，自由$0$有$j$个，自由$1$有$k$个的可行性

这个可以直接推

但是对于不同的状态，其0,1总数可能相同，直接统计有可能造成重复累计

于是考虑按从后往前的顺序只统计最先出现的0,1状态（因为相对而言后缀的长度越小，对最后的结果的要求越松，相当于从后到前的答案集合是包含关系）

继续设$num[i][j][k]$表示总共$i$个$0$，$j$个$1$，从后往前匹配到$k$的所有字串数，求出这个数组后对每个(i,j)从后往前枚举，只计算最后的答案即可

CF-GYM101630G（done）

二分答案便乘求方案数，考虑枚举x求满足条件的y的数量，可以主席树做

CF1326F2（untodo）

只考虑两人之间认识的限制，求出来的方案数是超集之和

相当于对n-1的每种划分数找链，求方案数

（然后不会了）

CF-GYM102538G（doing）

做一个生成树，正常的点分树只记录重心到黑点的距离，改成记录重心的和所有有跨子树边的其中一个节点到黑点的距离即可

一个分治块内的关键点到每个点的距可以暴力bfs

Quasi-template（todo）

建出SAM，可以预处理出每个等价类能够覆盖的[1,L]（也有可能没法覆盖到最前面，就忽略），之后就是原串后缀的前缀覆盖，对反串做kmp，border长度即为可以覆盖的最大长度

Isomorphic Matrices（todo）

套burnside.不动点个数为$k^{连通块数}$，对于一个行上环长为$x$，列上环长为$y$的一个矩阵，连通块数为$gcd(x,y)$，所以对于一个划分，总答案为$\prod_i\prod_j k^{gcd(x_i,y_j)}$，于是对于小维枚举划分数，对大维exp求$\prod_{j}k^{gcd(x,y_i)}$

CF-GYM102538D（todo）

因为这是一个排列，所以可以发现一个杨表对(A,B)（A表示值，B表示下标）和排列形成了双射，且相同形态的A与B的集合相同

于是划分数一下，然后钩子公式算出这种形态的杨表的方案数，其对应的排列数就是它的平方

钩子公式：$\frac{n!}{\prod_{i=1}^n{l_i+1}}$，$l_i$为钩子长度

CF-GYM102391E（todo）

二分答案后对仙人掌的dfs树树形DP，环的信息在深度最小的点处理。维护$dp[i]$表示在$dp[i]$中的最远距离$\leq mid$的情况下，以$i$为根，到$i$子树中的最远的点的距离。至于环，可以把返祖边以外的边拉在一条直线上暴力删边，变成处理前后缀信息.

TOPCODER12158（todo）

（待补）

LOJ3192（todo）

首先，被包含的桌子是可以删掉的，于是桌子在l单调的时候r单调。

其次，只考虑一个班，那么相邻高度的人挨着坐是最优的（考虑为一个班安排桌子）。

那么就可以为每个位置寻找最合适的桌子，使得这个位置对m组人费用最小

有决策单调性，可以二分

CODECHEF-TREEWALK（todo）

我们要求的答案矩阵即为$A^n$，由Cayley-Hamilton定理，设A的特征多项式为f(x)，则f(A)=0

所以$x^n~~mod~~f(x)$在$x=A$时为$A^n$

所以求出$g(x)=x^n~~mod~~f(x)$即可，这一步倍增可做

为此需要求出$f(x)=|xI-A|$，相当于在某个矩阵中选若干环

由于原图是树，故选$Len>2$的环是没有贡献的只需要考虑自环（单点）和2环（两个相邻点）

可以树形DP做

HDU5457（todo）

假设只考虑P操作，那么建出正向trie，问题即为ban掉树上的边，求root到leaf都不联通的最小代价

那么在P,S都有的情况下，同时建出正向和反向trie树，将相同的叶子结点连在一起，即求root_1到root_2的最小代价，最小割模型

LOJ2462（todo）

首先可以以每个点为根DP求出包含根的合法连通块最大权值和，以这个思路可以求出每个点/边能在多少个集合里充当重要点/连接重要点的边

由于任何情况下重要点均形成连通块，故每种情况的权值（即为1）能表示为1=点数-边数

换维（原本是按集合枚举点），为每个点/边算出其贡献，只需要$C(n,k)$，$n$为第一段求出来的值（即是所有能取的集合里取子集）

类似exlucas的计算$C(n,k)~~mod~~5^{23}$：

2021.8

8.2

网络流

Shoot The Bullet（todo）

裸题，直接感性建图

支线剧情（todo）

尝试对原图做网络流，每条边容量为$[1,inf)$，费用为$w_i$，为每个点加一条通往源点，容量为$[0,inf)$，费用为$0$的边，跑无源汇上下界最小费用可行流

Snuke The Phantom Thief（todo）

发现是前缀，多跑几次板子

面国修路

即最小化选择的边数，最大费用最小流

机场（todo）

做过/cy

GDOI2019 棋盘（todo）

待补

DAG

线性规划

线性基

围绕着我们的圆环（todo）

$$
\begin{aligned}
&C=AB\
列向量表示&A=(v_1,v_2,\ldots,v_q)\
列向量表示&C=(u_1,u_2,\ldots,u_s)\
&u_k=\sum{v_iB_{i,k}}\
方案数为~&2^{(q-r(A))s}\
r维线性空间，取一组基，&A每一列都是基生成，可以当成r维列向量

\end{aligned}
$$

https://www.cnblogs.com/daklqw/p/11508682.html

？？？

不是很听得懂

行列式

Determinant

对一个边双缩点，爆算（考虑到缩点出来的边永远不会被选）

Determination

没听懂

伴随矩阵

跳蚤猜密码（todo）

Cauchy-Binet 公式

Yet Another Linear Algebra Problem

发现$det(A*A^{T})$直接套就是枚举的过程

LGV 引理

Intersection is not allowed!

模板题

网格（todo）

终于听懂了/ll

考虑只有一条路径时的方案数，可以容斥DP：

$f[i][j]$ 表示在选 $i$ 的情况下任意选择必达节点集合（保证 $i$ 最后到达），总共经过了 $j$ 个节点的方案数

可以 $O(n)$ 转移，复杂度 $O(n^3)$

我们发现如果要两条路径不交，那必然是 $(0,1)\rightarrow(n-1,m),(1,0)\rightarrow(n,m-1)$

于是套LGV就可以了

Matrix-Tree 定理

作业题（todo）

有gcd求和，可以考虑反演（待补）
$$
\begin{aligned}

\end{aligned}
$$

欧拉回路计数（BEST定理）

$T(G)\prod_{i=1}^{n}{(out_i-1)!}$ ， $T(G)$ 表示以任意节点为根的内向树数量

奥林匹克环城马拉松（todo）

https://vfleaking.blog.uoj.ac/blog/1991

树边的定向必可确定

环上边只要为一条边定向就可以定向所有边

然后就直接套了

特征值、特征向量、特征多项式

若对实数 $\lambda$ ，有 $\lambda u=Au,u\neq \bold{0}$ ，则 $\lambda$ 称为 $A$ 的一个特征值，非零向量 $u$ 为 $A$ 的一个特征向量，所有 $u$ 形成的线性空间称为特征子空间记为 $V_\lambda$

$\lambda$ 为 $A$ 的特征值当且仅当 $|\lambda I-A|=0$，故设 $f(\lambda)=|\lambda I-A|$ 为 $A$ 的特征多项式，为 $n$ 次多项式，$f_A(\lambda)$ 中的重数称为代数重数， $\lambda$ 的特征子空间的维数称为几何重数，几何 $\leq$ 代数

$\sum \lambda=\sum A_{i,i}$ ， $\prod \lambda=|A|$

矩阵相似、对角化

若 $B=PAP^{-1}$ ，则 $A$ 与 $B$ 相似

相似不改变特征多项式、迹、行列式、特征值

若 $A$ 可对角化，则存在对角阵 $B$ 使得 $A=PBP^{-1}$，故 $B$ 的对角线即为 $A$ 的特征值， $P$ 的各列对应特征向量

8.3

转置算法

无reverseFFT

转置后一模一样，则可以对DFT转置，对IDFT不转置，则reverse抵消

转置算法多点求值

学会了，待补

CF-GYM102978D

学会了，待补

TREE&PRIME

设 $a_k$ 为金币数为 $k$ 个的贡献（0/1），$F_{i,j}$ 表示到第 $i$ 个点金币数为 $j$ 的概率，$b$ 为答案序列，则转置算法为
$$
a_k=\sum_{i=1}^n b_iF_{k},\F_i=\prod_{j\in Path(1,i)}{(p_jx+1-p_j)}
$$
直接求

（简单的思路是改变向量所乘的维度，感性地看）

组合计数1（todo）

引理(Prufer)：

有k个连通块，大小为ai，总结点数为n，加边形成生成树的方案数为
$$
n^{k-1}\prod a_i\
$$
又有
$$
g*2^g=(x+1)^g2^g=x^1^g
$$
于是设 $t=2x+2$ ，求
$$
\begin{aligned}
\sum_{T_2}[x^1]t^{T_1\cap T_2}&=[x^1]\sum_{T_2}(t-1+1)^{T_1\cap T_2}\
&=[x^1]\sum_{T_2}\sum_{E\sube T_2 &E\sube T_1}(t-1)^{|E|}\
&=[x^1]\sum_{E\sube T_1}(t-1)^{|E|}|E\sube T_2|\
&=[x^1]\sum_{E\sube T_1}(t-1)^{|E|}n^{k_E-2}\prod_{i=1}^{k_E}{a_E}i\
&=\sum{E\sube T_1}([x^1]\sum_{i=0}^{|E|}\binom{|E|}{i}(2x)^i)n^{k_E-2}\prod_{i=1}^{k_E}{a_E}i\
&=2\sum{E\sube T_1}|E|n^{k_E-2}\prod_{i=1}^{k_E}{a_E}i\
\end{aligned}
$$
可以记dp数组 $f{i,0/1}$ 表示第 $i$ 个点子树内考虑/不考虑第 $i$ 号点所在连通块的答案（我猜的，写的时候再说）

无了/kk

组合计数2（untodo）

康拓展开能展开成各位之和，$|b_i>b_j\and i<j|*(n-i)!$

枚举每个a_i求出其位置j的概率乘期望

对每一轮每一个数分析贡献：
$$
\begin{aligned}
&\sum_{k=0}^{\infty}\sum_{l=0}^{i-2}\sum_{r=0}^{n-i}\binom{i-2}{l}\binom{n-i}{r}(n-l-r-1)!(1-q^{k+1})^l(1-q^k)^rq^{(k+1)(i-1-l)}q^{k(n-i-r)}pq^k\
&令q^k=t,i!=u^i\
原式&=\sum_{l=0}^{i-2}\sum_{r=0}^{n-i}\binom{i-2}{l}\binom{n-i}{r}u^{n-l-r-1}(1-qt)^l(1-t)^r(qt)^{i-1-l}t^{n-i-r}pt\
&=pqut^2(1+qt(u-1))^{i-2}(1+t(u-1))^{n-i}\
&设v^{\dot{}}=u(u-1)^{\dot{}},x^\dot{}=t^2(tv)^\dot{}\
原式&=pq(1+qx)^{i-2}(1+x)^{n-i}
\end{aligned}
$$
即求 $x$ 的系数

然后转置/fad/fad/fad

然后不会了/kk/kk

SAM

你的名字（todo）

裸的parent树上统计答案

线段树合并和树剖都能做

LUOGU4482（todo）

$len(lcs(y,r))\geq y-l+1$

则变成 $l + len(x) > y$

考虑离线，树链剖分对每个重链开个堆记录其轻子树中的查询。在每次 $r$ 加入时把 $(l+len(x),id)$ $O(log^2n)$ 加入

查询时让$y$ 跳重链，每次把重链里比 $y$ 大的全部取出来（已经被取过直接pop），也是 $O(log^2n)$

runs

$r=(i,j,p)$ 周期为 $p$ ，区间为 $[i,j]$ 的极长循环串，且最少循环 $2$ 次，且 $[i,i+p-1]$ 非周期（既没有比 $p$ 小的周期）

长度为 $n$ 的字符串的runs最多有 $n-1$ 个

对于非周期的串 $s$ ，有一种循环移位是lyndon串

对于一个runs，存在长度为 $p$ 的子串为lyndon串

$l_t(i)=max{j|s[i,j]在<_t的意义下为lyndon串}$

对于 $s_{j+1}<0s{j-p+1}$ ，$l_0(a)=b$

$l_0(i)=iorl_1(i)=i$

求法：duval算法

CF446D（todo）

首先想办法处理出所有限制点不经过别的限制点时互相之间的可达概率，之后就可以矩阵快速幂

考虑dp，首先对所有限制点求出每个非限制点不经过限制点到它的概率，写成方程组的形式

发现每次系数矩阵完全不变，只有常数矩阵改变，于是可以扩展未知数向量和常数向量至矩阵

然后对于限制点到限制点就可以直接推了

8.4

ZRA1-A

对每个点按切比雪夫距离从内到外枚举答案，总共是 $O(n^2)$ 的

ZRA1-B

对于一个矩形，可以选择两个边缘；考虑把一个图分成很多矩形，则易知只需要选择一半的轮廓，找找规律可知答案为 $C/2+1$ （C为周长）

考虑每次找一个外围的点，可以发现如果删掉这个点周长不变，则这个点不会贡献；如果删掉这个点周长-=2，则会贡献

如此贪心即为正解

ZRA1-C

慢慢写

概率期望

$\sum_{i=1}^{n}\frac{n}{n-i+1}$
$\frac{1}{i}$
$\sum_{i\neq j}{\frac{2}{ij}}+\sum{\frac{1}{i}}$
$\frac{1}{2}$
$\frac{1}{m!}$ / $\frac{(n-m+1)!}{n!}$
$1+\sum_{i=2}^{n}\frac{a_i}{a_1+a_i}$
$E_i(X^2)=p(E_{i-1}(X^2)+2E_{i-1}(X)+1)+(1-p)E_{i-1}(X)$
$\frac{2}{(i-j)(i-j+1)}$
$$
建出DAG，题目即为入度为0的点选完的期望次数

8.6

CF446D

建新图只有关键点，枚举所有关键点跑出所有非关键走到他概率，列出方程组发现所有的系数矩阵都是一样的，可以矩阵求逆

ZRA3-A

柯西/单调性凸性/whk数学/乱搞

ZRA3-B

支配树，一个点必经的所有点都在其到根的路径上

BFS出一个DAG 在DAG上一边建树一边缩点，和s缩到一个部分的点答案为0 否则答案为1（不连通特判）

ZRA3-C

1.$\sum len_i\leq 210^5\Longrightarrow count(len_i)=O(\sqrt{210^5})$

所以在AC自动机每次往上跳，关键点只有 $O(\sqrt{n})$

AC自动机每个关键点记录第一个关键点祖先即可

$O(kn\sqrt{n})$

2.考虑在SAM上跑所有的t串，可以串长分块，对于 $>\sqrt{n}$ 的串暴力DFS；对于 $\leq\sqrt{n}$ 的串可以在parent树上暴力维护数组

8.7

ZRA4-A

线段树合并求出以每个点为中间点的方案数/主席树维护DFN上的数据

ZRA4-B

可以设计DP： $dp[i][j][k][l][m]$ 表示总点数，度数为0,1,2,3的点的个数的方案数，可以 $O(Kn^5)$ DP

但应该发现其不保证所有点连成连通块

设 $G(n)=\sum_{i,j,k,l} dp[n][i][j][k][l]$ ，表示不保证联通的方案数， $F(n)$ 表示保证联通的方案数

则有 $F(n)=G(n)-\sum_{i=1}^{n-1}\binom{n-1}{i-1}F(i)G(n-i)$ ，即是 $F(n)=\ln G(n)$ ， $O(n^2)$ 解决

ZRA4-C

数据随机，联想到生日悖论，取 $\sqrt{p}$ 个点时得到正解的概率极大

于是可以每次取不同的随机点值， $O(n\sqrt{p})$ 解决

发现每次选点求一次点值效率太低，发现DFT即是求单位根的点值的过程

于是可以选这 $O(n)$ 个单位根的点值作为点值，正确率极高

8.8

ZRA5-A

使用之前的结论，推一下规律（周长/田字格）

ZRA5-B

首先，可以DP： $f_{i,j}\rightarrow f_{i,j-c_{k,i}},f_{i,j}\rightarrow f_{i-1,j*a_{i-1}}$，其中$c_{k,i}$ 为 $k$ 物品在使用 $i(i\geq d_k)$ 种货币时向上取整的价值

之所以能想到这种转移，是因为数据过大无法全部转化为某一种货币，可能需要面值从大到小分层转移

这样做会发现 $\sum_{i}c_{k,i}$ 是 $O(c_k)$ 的（每次减少一半），于是每一层暴力分治NTT即为答案

ZRA5-C

原理：点集划分

首先明显地确定了 $a,b,c$ 的任意一个以后就可以在 $2n$ 次内找到答案

那么我们需要先随意选择一个点： $x$ ， $n$ 次查询出其连边

$d(x)=n-2$，则 $c=x$ ，则可以在之后 $n$ 次确定 $a,b$ ；
$d(x)\leq 2$，则 $x$ 有可能是 $a,b$ ，则在 $2n$ 次内找到 $x$ 的邻点的连边，然后对这至多 $2$ 个点判断 $a,b,c$ ，则必有其中一个，之后至多 $2n$ 次找到答案；
$3\leq d(x)\leq n-3$ ，则该点一定和 $c$ 相邻，一定不和 $a,b$ 相邻，与 $a,b$ 相邻的点只会有 $c$ ，然后划分出相邻与不相邻的两种点集，每次在这两个点集中最多 $n$ 次选点查边，若有边，则删掉不相邻集的该点，否则删掉相邻集的该点，最后两个点集一定只有不相邻集非空，则最后使用的点就是 $a$ ，然后 $2n$ 次过.

ABC213G

裸的状压DP

设计状态为 $f(S)$ 表示 $S$ 形成连通块的方案数，则一次容斥，经典地枚举与 $x$ 相连的连通块个数，再设 $g(S)$ 表示随意选择 $S$ 中边的方案数，则有转移 $f(S)=g(S)-\sum_{x\in T}f(T)g(S-T)$ ，于是就可以愉快地AC了

ABC213H

首先明显是多项式，根据题意可以直接对该图的多项式矩阵做快速幂，但明显 $O(n^3Tlog^2T)$ 的复杂度不能满足我们的要求

考虑优化，题目中最明显的一个性质即是起点和终点都是1，所以每次更新只枚举最后走的边，即设计DP
$$
f_{i,j}=\sum_{k\in E,i\in k}\sum_{l=0}^j f_{to_k,l}p_{k,j-l}
$$
明显是一个卷积的形式，列为多项式的形式
$$
F_i(x)=\sum_{k\in E,i\in k}F_{to_k}(x)*P_k(x)
$$
这个式子为在线DP，不能直接FFT

但是我们注意到每个 $[x^0]F_i$ 都确定，每个 $P_k$ 都已完全给出

则可以分治FFT，具体来讲，就是最外层套CDQ，每层分治跑一边图上的全部卷积

妙啊

$O(mTlog^2T)$

8.9

ZRA6-B

假设该图是无向图，则在在该图上找到一个环作为其哈密顿回路，则环外的边都可以抽象为偏序关系

我们尝试从排列映射到无向图的集合，方法是将排列首尾相连变成环，根据排列每个点对 $(i,j)$ 的偏序关系判断边 $(i-1,j)$ 能否存在于原图中

ban掉的偏序关系即为逆序对。所以答案就变成求n排列的q的逆序对数次方和了

柿子：
$$
\begin{aligned}
&p^n\sum_{i=2}^{n-1}(1-p)^{i-2}v_i\sum_{j=i+1}^{n}(1-p)^{n-j}v_j\sum_{p_{n-3}}(1-p)^{\sigma(p)}\
\end{aligned}
$$

ZRA6-C

枚举 $j$ ，对每个 $i$ 找到一个 $k$ 的取值区间 $[f_i,g_i)$ 则答案为 $\sum max(g_i-f_i,0)$

CF1557D

DP式子为 $f_i=\max{f_j+1}$ ，直接维护横向的线段树，每次区间修改即可

CF1557E

考虑把国王逼到第 $8$ 行的角落。先把皇后放在 $(1,1)$ ，则皇后覆盖的方格将把网格分为2个块

每次纵向移动皇后，若在这个过程中国王向下走，则皇后也向下走；若走到底国王都没向下走，则国王位于下半块，此时就向下走反方向遍历纵向就好了

8.10

ZRA7-B

拍到dfn上相当于求 $\sum_{i=l}^{r+1}[a_i>a_{i+1}]=0$ 的点数，每次修改都是在将某点往上跳更新每个节点，可以直接树剖

8.11

ZRA8-B

考虑在PAM上DP，算出以每个状态 $u$ 的答案，乘上size

每个 $s_{i}$ 可以由 $s_{i-1}$ 将l/r边界的其中一个移动，然后取前缀/后缀得到

于是设计DP：$f_{i,0}$ 表示 $s_1=i$ 的方案数， $f_{i,1}$ 表示 $[l_i,r_i]$ 中所有回文串的方案数总和， $f_{i,2}$ 表示$ [l_i,r_i]$ 中至少卡着一个边界的回文串的方案数总和， $f_{i,3}$ 表示 $[l_i,r_i)$ 的所有回文串的方案数总和（和 $(l_i,r_i])$ 等价）

$p_i$ 表示PT上的father， $b_i$ 表示parent树上的father
$$
f_{i,0}=f_{p_i,1}+1\
f_{i,1}=f_{i,2}+f_{j,1}\
f_{i,2}=f_{i,0}+2f_{b_i,3}+2f_{b_i,0}\
f_{i,3}=f_{b_i,3}+f_{b_i,0}
$$

8.12

ZRA9-B

假如两个点的最短路到达了同一个点，则该点以后两点的最短路将会重合。

那么我们尝试分析求最短路的过程，则若对于某个点1比2先到则将其设为 $l$ （若对2来说该点在最短路上，则对1来说经过该点的路一定比其短；否则对1来说这条路选为 $l$ 更优）；若对于某个点1比2后到则将其设为 $r$ 。

同时到需要分类讨论：若需要判断WIN，则要尽量使2经过的路径尽量长，故使之为 $r$；若需要判断DRAW，需要阻止2从另一条路径到达，故使之为 $l$

8.13

ZRA10-B

首先有 $x^2\Longleftrightarrow \log_2\log_2x+1$

8.14

[FJOI2014]病毒防护带

写出点到直线的距离公式，发现这个式子看着就很凸

直接三分套三分

证明用偏导

[FJOI2014]树的重心

假设只有一个重心，其将整棵树分成许多子树，一个连通块必然是在子树里选，则必有 $siz_v\leq \frac{1}{2}\sum{siz_u}$

然后可以发现有两个重心的情况，一定是在把两重心之间的边看做一个点的前提下，该点两个子树大小相等，同样符合上式

先dp出每个子树选择每种点数的方案数（ $O(n^2)$ ），然后再做一遍背包，正反两遍合并背包（ $O(n^3)$ ），之后 $O(n)$ 枚举子树，每次 $O(n^2)$ 合并背包

这样会算重，但算重只有可能是2个子树大小相等，只需要 $O(n^3)$ 枚举子树对和大小

2021.9

8.24

AGC001F

对于这一DAG不能直接贪心选取最小，因为这是逆排列，有字典拓扑定理：

对于任意一个DAG的一个拓扑序 $p$，$p$ 最大是 $p^{-1}$ 最大的充要条件；最小则不满足。

脑补得证

所以在反图上求最大拓扑序即可，然而不能直接建图

考虑对于一个点，其入度为 $(p_i-k,p_i+k)$ 内序号大于它的数个数

这个东西可以通过权值线段树/set初始化

然后每次找 $[1,n]$ 区间内 $(in_i,i)$ 第一关键字最小的前提下，第二关键字最大的元素，可以线段树维护，每次修改相当于对 $(p_i-k,p_i+k)$ 内的全部元素度数 $-1$，$p_i$ 处度数赋值为 $\infty$

8.25

AGC002F

可以转化为放置 $n$ 个白球和 $n(k-1)$ 个彩球，保证对于每个前缀位置有白球个数 > 彩球种类数

发现这些限制只与白球和每种彩球的第一个有关，于是考虑dp，设 $f_{i,j}$ 表示放了 $i$ 个白球和 $j$ 个第一个彩球

转移分为两部分：

放置白球，直接贡献 $f_{i,j}+=f_{i-1,j}$
放置彩球，枚举彩球的种类，并且选择序列之后的某些位置放置这种彩球 $f_{i,j}+=f_{i,j-1}(n-j+1)\binom{nk-(j-1)(k-1)-i-1}{k-2}$

就做完了

AGC003E

好他妈弔。。

发现对于 $n_i\geq n_{i+1}$，$i$ 是无用的，所以只用记录后缀最小值就行了

从后往前考虑，划分为子问题，有 $ans_i=\lfloor\frac{n_i}{n_{i-1}}\rfloor ans_{i-1}+ans_{i-1}[1,n_i%n_{i-1}]$

对于加号前是直接递归，对于加号后最大化一个 $pos$ 使得 $n_{pos}\leq n_i%n_{i-1}$，则又可以划分为 $X=\lfloor\frac{n_i%n_{i-1}}{n_{pos}}\rfloor ans_{pos}+ans_{pos}[1,(n_i%n_{i-1})%n_{pos}]$（若不保证pos最大，则不能保证 $n_x$ 之后的元素满足他的性质）；若找不到则可以直接在原序列上进行贡献（右端点落在原序列上）

右边的子问题递归 $O(\log n)$ 次（取模的性质），每次总共有 $n$ 次递归，所以总的复杂度为 $O(n\log^2n)$

直接递归复杂度是错的，从小到大求不好求，所以从大到小枚举，每次为之后所有的 $ans$ 累计贡献次数

做完了

AGC004F

大力分类讨论

I. $n$ 为奇数

黑点数每次变化2，无解

II. $n$ 为偶数

A. $m=n-1$

树是二分图，所以可以黑白染色，新树的规则变为不同颜色的点可以交换颜色，目的是让黑白点交换

于是染色后如果黑白点数不一样则无解

否则对每条边分析贡献，为 $|a-b|$ ，分别为子树内的黑点数/白点数

B. $m=n$

考虑拆边

1.$\ $环长为偶数

拆出来的边仍然是颜色不同的点交换颜色

于是会发现其连接的两个点到他们的lca的两条链分别加x和-x，就约等于一个 $\sum |w_i-x|$ 直接上中位数

2.$\ $环长为奇数

拆出来的边只能把同种颜色的点转换颜色

于是只要要求黑白点数差值为偶数即可

平衡黑白点之后这条边就没用了，转换成了树

AGC005D

先容斥，$f(x)$ 表示钦定 $x$ 个位置满足 $|p_i-i|=k$ 的方案数

ARC114C

拆下贡献呗

相当于一个连通图中(i,j)要联通需要其之间的数全部大于等于他们，最终就是统计连通图的个数

对每一对(i,j)计算他们联通的方案数，用全部的方案数减他们就是+1的贡献次数，可以直接算

8.30

ZRNOIPA1-C

其询问为序列的种类数，而序列的每个位置只和SCC个数有关（而非SCC的大小、形态之类），因此考虑进行构造。对于一张图，让其加边，有三种可能，一种是全加在SCC中，序列下一项不变；一种是加在SCC与SCC之间但不形成新的SCC，序列下一项不变；一种是加在SCC与SCC之间，序列下一项要减一个数。

要求序列的形态最多，即是要求前两种情况能加的边数最多，且第三种情况能够缩进去的SCC最多。

对于前者，考虑总共有 $m$ 个SCC，那么 $m-1$ 个1，$1$ 个 $n-m+1$ 能提供最多的空位

对于后者，在同样的图的情况下，优先把SCC连成链，一条边能缩的SCC最多

所以考虑DP $f(i,j,k)$ 表示已经加了 $i$ 条边，在最大的SCC内有 $j$ 条有意义的边（即DP过程中加进去的边，明显是 $O(n)$ 的；不用记录具体有多少边的原因是只用找最优化的图而非记录图的个数），最大的SCC大小为 $k$：（那么SCC连成的链长为 $\min(i-j+1,n-k+1)$）
$$
f(i,j,k)\rightarrow f(i+1,j,k):i+1\leq \frac{k(k+1)}{2}+\frac{(n-k)(n-k+1)}{2}\
f(i,j,k)\rightarrow f(i+1,j+x+1,k+x):x\in[1,\min(i-j+1,n-k+1)]}\
%f(i,j,k)=f(i-1,j-x-1,k-x),x\in[1,max(k,)]
$$
这个式子的状态是 $O(n^4)$ 的，转移可以前缀和优化

8.31

ZRNOIPA1-D

首先，事实：对于一个异或和为0的集合，其任意子集的异或和相等

那么就很明显了：只有当所有数异或和为0，才会平局

然后从高到低位考虑，显然只需要考虑最高位有奇数个1的位

接下来相对比较难判断，考虑能否分类讨论

当n为偶数时A和B取的数字个数相等，于是手玩发现A和B分别能取到奇数和偶数位置的数（这两个集合一定分别是0/1），而这是A决定的，所以A必胜

当n为奇数时，比较容易转化为偶数，继续分类讨论

当两边都是0：一定转化为偶数的情况，先手必败

所以如果两边有1，则先手一定会选1，转化为了偶数个位置偶数个1的情况

考虑一种避免必败的策略

如果B选了0：A必须选0，否则进入必败

如果B选了1：A必须选1，否则进入必败

那么把两边相等的东西删掉以后一定只有2个极长连续段（手玩）

做完了（好长（大嘘））

[口胡记录]ARC115

迫真口胡前20min rush：

A(1min)：M只有20，异或之后数1的个数

B(4min)：对C的每一行做差分，看数组们是否相等，然后无脑构造

C(6min)：相当于求mex，显然不能暴力求。但是发现对于一个数可以直接贡献到它的倍数，因为可以保证如果这个点的 $f$ 为 $x$，则其一定有 $f=x-1$ 的某个因数，并且这个数一定会贡献到其能贡献到的地方

D萎了

20min-30min rush：

E(26min)：做很多次前缀和（？）

ARC115D

对于欧拉回路有一个结论：

对于一个图 $G$，其DFS树上任意树环（只包含一个非树边的环）的异或图（所有边的存在性性异或起来）都是欧拉回路

于是就能保证所有k个点度数都是奇数，所以式子是：
$$
\binom{n}{i}2^{m-n+1}
$$
对每个连通块跑一遍卷起来就行了

ARC115E

应该可以线段树维护交错符号的前缀和，应该是 $O(n\log n)$ 的

但是有 $O(n)$ 的解法

考虑容斥，$g(t)$ 表示分成t段相等段的方案数，容斥系数为 $(-1)^{n-t}$，所以可以直接dp $f(i)=-\sum f(j)*\min{a_k}$

$\min{a_k}$ 可以单调栈维护

ARC115F

暴力的思路：生成k元组表示k个点所在位置的状态，能够建出新图；即是在新图上跑瓶颈路

然后考虑二分，就变成了求可达性

发现二分的过程就是选取上界的过程

而对于一个新图上的路径，一定有一个最小值，我们就考虑从两边贪心地往这个最小值上靠

（鸽）

9.2

deleted

9.3

[vp记录]ARC123

咕咕咕

[省选联考2021]矩阵游戏

首先可以明显构造出一个不合法解

然后考虑调整（*没有想到调整法，转而思考对边界元素的限制，差分约束->一般线性规划，得不偿失）

发现针对行/列可以交错符号地调整，能保证b不变

于是对每一行/列设置一个参数，对每个位置有一条边，变成了差分约束

注意每相邻行/列符号交错，否则会有和式

9.6

[HNOI2017]礼物

推下式子发现常数的选择是固定的

于是就变成了最大化 $\sum x_iy_i$

把 $y$ 翻转就变成了卷积的形式，裸的FFT

9.7

[HNOI2017]大佬

关键点：能够发现直接BFS求出所有怼的可能复杂度是对的（*完全没有往这边想。。。有的时候确实应该多想想弔方法）

然后就求出了若干数对 $(d,f)$ ，其中d是使用的天数，f是打出的伤害

没有怼、1怼好求

2怼：$f_1+f_2\leq C\and f_1+f_2+(D-d_1-d_2)\geq C$

根据单调性枚举f1，然后求出满足条件的f2并使得f2-d2最大（前后缀最大值）

[HNOI2017]单旋

找规律（*其实可以通过最值只有一个儿子来推，但是脑抽了推的是一般情况）

然后对每个点记录他的父亲和其中一个儿子，就能直接线段树维护

[HNOI2017]影魔

考虑每个点，求出他能作为最大值贡献的区间 $[l_i,r_i]$

然后就是水水题了，可以离线+BIT做，也可以树套树

9.8

[HAOI2017]供给侧改革

考虑后缀树（*因为有随机这个条件，所以可以优先考虑后缀树的树形结构（树高为 $O(\log n)$；而某sb只会后缀数组。。。）

然后考虑离线（干啥啥不行，离线第一名.jpg）按R升序排序

维护一个数组 $a_i$ 表示L=i时的答案

那么对于每个加进来的数暴力跳祖先，对每个点维护它的endpos集合，然后在集合中找到R的前驱，更新 $a[1,i]$

不用担心R所在的子树被重复统计，因为这根本不会影响结果（弱智x）

upd：不需要维护endpos集合，这样会徒增一个log；因为可以直接在统计后把R加入所有的祖先中（捂脸）

9.10

[NOIONLINE2021]岛屿探险

首先，考虑子任务5,6,7

即求 $a_j\text{xor}c_i\leq d_i$，只有左边与j有关，于是考虑建其区间的01trie，可以分层做到 $O(\log n)$，然后多个操作整一个可持久化01trie即可

考虑子任务8,9,10,11

$a_j\text{xor}c_i\leq b_j,j\in[l_i,r_i]$，发现这个东西是和上一个东西对称的，于是可以把询问的l_i和r_i扔进2个01trie，然后把数当做询问做一个加权的上一个子任务

但是在100%的数据中，第一、二子任务都会出现，区分的条件是b和d的大小关系

于是就可以把数和询问都塞进一个数组做CDQ分治，然后讨论左对右的贡献，建01trie就能做到 $O((n+q)\log m\log(n+q))$

就对力

9.12

CF618G

看不懂（悲

9.13

[SDOI2019]染色

考虑一个只有空点的情况，可以轻易推出柿子

然后考虑分段，就变成了左右有限制的全空点

然后由于每段的左右都最多有 $O(m)$ 个状态

所以可以用奇技淫巧的线段树维护

但是看着难写

[CTSC2017]最长上升子序列

首先可以Dilworth转化为求最小不降子序列覆盖

发现这个东西就是前缀的杨表的前k行数字的个数

但是这么做是$O(nr\log c)$ 的

考虑杨表是一个块，所以r和c至少有1个不会超过 $O(\sqrt{n})$ ，所以可以每次只枚举到 $\sqrt{n}$ 层就不累加了，然后枚举它的转置变成前k行就行了

9.15

[JXOI2018]守卫

被你妈骗了。。。

首先考虑DP，很简单，不用讲（*其实思考的时候有点小锅，要从第一个合法点开始转移才对）

然后怎么求第一个合法点就开始瞎想了

你妈，直接从后往前枚举左端点就好了（*你妈的凸壳）

[PKUSC2018]最大前缀和

思考枚举前缀最大值的位置（最后）在哪里

然后有以下作为充要条件：

1.这个位置后面的前缀和全部小于0

2.这个位置前面的后缀和（除去a1）全部大于等于0

然后考虑两边分开求，然后合并；另一种意义下，这样的转化使得复杂的条件变成简单条件的组合，符合我们的本意

这提供了区别于转化枚举顺序的另一种优化思路：转化题目条件

这样就变成了三次状压DP力

9.16

[PKUSC2018]星际穿越

首先对于每个点向前遍历节点代价是递增的

然后想到了数据结构维护当前点向前的函数，但是明显不好维护

然后可以发现向右走一步就是向右走的极限（想一想，为什么），所以可以直接定义一个位置的函数即为当前位置后缀的函数

发现这个函数可以由多个左端点描述，而确定了第一个左端点以后就可以划分为子问题

于是就可以倍增出每个点的2^i-th左端点

考虑询问：

然后把询问拆成 $[l_i,x_i)$ 和 $(r_i,x_i)$ 两部分

那么仔细理性地思考，发现这个东西可以直接倍增求（因为左端点在有节点跳跃的情况下也是连续的，逼近的过程仍然是 $\log n$ 的；区间的询问可以同时处理，每次对相应的长度实施+1即可）

最后注意一步到达的点要特殊处理

然后就做完了

（*对倍增没有感情，想到了倍增数组和拆分，然而不只是区间查询了，就连单点查询的可行性都不明晰，对于这样的问题，要先问问标准的倍增能不能做，不要复杂化）

9.17

[THUSC2017]随机二分图

第一步，转化枚举顺序！！！

先明晰题目给出的式子以图为维，计数 $\sum P(G)n(G)$

可以先枚举完美匹配（$O(n!)$），计数 $\sum P(permutation)$ （把上式拆开重新组合，老套路）

（*直接莽，没有思考，直接奔着积和式去了，结果推出一堆屎；然而这一步以后就很通畅了，说明模型转化的能力十分重要，也是我需要克服的短板）

然后瓶颈在于枚举排列，考虑状压DP
$$
f_{S,T}=[|S|=|T|]\sum_{u\in T} f_{S-max(S),T-u}g_{S,T,<max(S),u>}
$$
（当然，可能需要取出两条边，这里为了方便不考虑）g表示当前点集内加入一条边对概率产生的贡献，很好求

这个东西是 $\sum_i \binom{n}{i}^2=\binom{2n}{n}$，大约是1.5e8的数量级，然而明显卡不满

于是复杂度就是 $O(\binom{2n}{n}n)$ 的

9.23

郁金香

很有意思的莫队题

首先由出现次数想到莫队

移动端点维护出现次数数组，并对每种出现次数维护出有多少种数字，这样就可以二分答案找到答案的出现次数

O(1)维护答案比较困难，考虑logn的做法：对每个答案开一个平衡树，维护最小值

这种做法的时间复杂度是$O(n\sqrt{n}\log n+n\log n)$，因为修改操作次数是 $O(n\sqrt{n})$ 的，而查询操作是 $O(n)$

这启示我们寻找一个修改 $O(1)$，查询至多 $O(\sqrt{n })$ 的做法

明显可以数值分块，$f_{i,j}$ 表示出现次数为i，数值位于j块的数字个数

总的时间复杂度为 $O(n\sqrt{n})$

CF1476G

牛逼莫队题

首先这是个裸的三维莫队，具体不讲，可见上一个题解

那么问题来了，统计出出现次数数组和其逆数组以后咋办

很不好维护

但是记得另一个根号结论：和为n的不同数数量为 $O(\sqrt{n})$

于是逆数组的点值总共只有根号渐进种选法

于是我们可以直接运算的数组的长度就变成 $O(\sqrt{n})$ 的了，维护带不带log都无所谓，毕竟有个5/3

$O(n^{\frac{5}{3}}+n^{\frac{3}{2}}\log n)$

CF700D

神仙莫队题，有价值

很明显是一个霍夫曼编码的问题，最大化 $\sum c_id_i$

这个问题可以通过脑补霍夫曼树并应用堆的方式做到一次查询 $O(n\log n)$

但是不太行

我们考虑在 $c_i$ 维上分类讨论，设阈值为 $B$

对于大的数可以直接上堆，复杂度 $n/B\log(n/B)$

对于小的数可以转化为出现次数维上的问题，这个东西是可以模拟堆来合并的，需要注意的是当合并出来超出范围了，直接扔到上一种情况，对其复杂度不会有影响（因为总的数字的个数不超过n），这种情况的复杂度为 $O(b)$

总复杂度为 $O(q(B+n/B\log(n/B)))$，可以，均起来了，B取$\sqrt{n\log n}$ 就能做到 $O(q\sqrt{n\log n})$

9.28

[ZJOI2017]仙人掌

（*被骗了，又想到矩阵去了，中途还乱想了一堆，最后得亏是迷途知返才想出来。。）

首先随便加一个边，发现这个边一定会在一个环里

所以加的边不能跨环，原图就变成森林了；且每个树边明显只能被一个新边覆盖，就变成了树上链覆盖问题了（*不用考虑链长是否要>1，因为当链长=1时这条边不选）

然后就直接DP就行了（要先DP出对于一个菊花心匹配其连边的方案数）

9.29

[ZJOI2017]树状数组

（*你妈，老傻逼了）

批斗：

首先每一段的概率之间明显不是独立的，故不能直接贡献，所以线段树做法驳回

其次这个东西是个后缀和，简直不能不看出来

最后他计算两个端点的贡献的时候必须要用树套树/CDQ，结果并没有认清形势，放弃幻想

解：

首先转化为求两个点相等的概率

然后树套树直接维护(l,r)的概率，不要维护修改啥的（*）

CDQsb

[ZJOI2017]字符串

分块+hash+结论

不要一遇到后缀排序就sa啊kora

Significant Suffix最多只有 $\log n$ 个

然后用线段树维护每个 $[l,r]$ 的特征后缀集合

然后求LCP用字符串哈希

然而线段树维护哈希要4个log

所以哈希分块维护

9.30

[CSP-S2020]贪吃蛇

再来看显然不难

首先思路比较好想，就是先假设这个蛇要吃，再判断是哪一步不能选择吃

需要注意的是如果某一步某一个蛇可能会被吃不能着急跳出，要看之后吃它的那一步会不会被选

然后维护显然不能用堆

发现每次max-min是单调不降的，所以开俩deque就行了

2021.10

10.8

ARC106E

有点意思

首先他明显能转化为一个二分答案

然后由于其复杂性难以运用简单算法

故转化为同样复杂的图论模型：

考虑一个 $NK+D$ 的二分图，NK是一个人的某个奖牌，D是天数

将每一天连向这一天能颁发的奖牌（每人K个都连），那么就是求一个左部为NK的二分图是否有完美匹配

那么就便乘了霍尔定理

对于一个集合，它的对应集只取决于这个集合中有的人

那么对于一个人的集合，就要满足
$$
|S|K\leq F(S)
$$
其中F(s)表示在D天内能覆盖的天数

这个东西可以 $O(N2^N)/O(N2^N\log NK)$ 求

*没想到能这样转化（小本本……），二分图经验不够（摊手）

ARC106F

什么神仙构造方法题。。

考虑一种构造：

对每一个点取一个被标记的洞

重复n-2次：

选一个没被标记&没选过的洞
再选一个被标记&没选过&和上一个洞不在同一个点的洞
连起来

最后把剩下的俩标记的洞连起来

这种构造方法构造出来了一个会算重的方案，考虑去重：

考虑对一棵没有标记的树做标记

选一条两端都被标记的边，从这条边向外延伸可以唯一确定一种标记方案
这条边永远是最后加入的，剩下的边加入顺序可以随便编排

于是就变成了每种边的排列都有可能被算上，同时除以 $(n-1)!$ 就行
$$
\prod d_i \prod_{i=1}^{n-3} (S-n-i)
$$
*一直在想生成函数和prufer序列，推出一大堆发现不会

*思维方面不够活跃，容易陷入套版

仔细想想，这个方案的构造和prufer序列有异曲同工之妙

但总之这种染色+除法原理的巧妙解法值得运用

10.9

Codeforces Round #747 (div.2)

太sb了

写一半没保存蓝屏。。

CDE1E2F都能一眼秒

AB反倒是想了半天，8min/18min

一看榜一是3min/2min，笑拉了

接下来是震撼人心的8次罚时400分，C2次D3次E1 3次，属实是牛批

C和D都算了，E1一个裸的式子能WA3次是赶着去投胎吗

然后是D，咋都不该写挂的

C写挂也是，哪能这么急啊

结果导致不禁被罚时，写的还慢，E1 90min才搞定

然后E2和F更精彩

看了E2会做直接跑去写了是吧

结果写不出来，属实难写

然后才去看F，发现是sb规律题，属于是出题人献祭亲妈了

也就剩60秒了，没蚌住

属于是喜提1000+了

CF1575M

首先先一排一排的看

然后把式子拆一下：
$$
(x-x_i)^2+(y-y_i)^2=x^2-2xx_i+x_i^2+(y-y_i)^2
$$
这是一个二次函数，多个二次函数求最值，直接斜率优化

CF1575B

很简单

二分半径长度

然后脑补一个顺时针方向转动的圆，按所有点进入这个圆的先后把点排序

再按所有点出这个圆的先后把点排序

然后加点删点就能判断最大能有多少点了

2021.11

11.16

ZR20day18C

可以考虑对于一个点i有[l,r]，则[i,r]的所有点的右端点<=r

所以当只考虑右端点时，记忆化地暴力往左右两边跳（不论顺序）是O(n)次的

左端点同理

所以最终是O(nlogn)

ZR10day10A

首先转化为差分的形式，就能变成两个点之间连边

然后就是要在一个图内选择边，使得每个点的度数和点权奇偶性相同

这是个模型，可以先考虑一个生成树，然后思考每种非树边的选择方法里，能用树边平衡的方法

很明显就是 $2^{非树边条数}$

ZE10day10C

首先明显横竖是独立的，因为假设横着折一个位置，其合法性不会随纵着折了多少次而改变

然后hash一下就变成了对一个字符串判某个子串能否被折出来

一个很自然的想法就是分开考虑其左右端点

对于某一个缝，我们考虑让其作为左端点，首先要使得其回文半径接触左边界或内有另一个合法的点

然后考虑对于任意一对合法的左端点和右端点

把需要折的位置在串上标注出来，则从外往内整一定是对的（否则考虑abc|de往左折，显然最右边被折过的那个数既是a也是e，如果a=e，则ab之间能再折一次）

所以只用manacher+统计就行了

ZR20day18D

证明引理：

$\exist t,a_t=max(a_i)\rightarrow b_t=max(b_i),a_t-b_t\geq max(a_i-b_i)-1$，其中a是直接把区间放上去的序列，b是被取消次数的序列

如果存在 $a_j\neq max(a_i)$ 却满足之后的条件，说明 $a_j$ 被取消的次数比 $a_t$ 多，于是就可以把某个 $a_j$ 被取消，而 $a_t$ 没有的给补上（且可以证明所有满足条件的t一定在所有被取消的区间的交里）

所以只要找到了$a_t$，就可以二分 $c=max(a_i-b_i)$ 求解

那么从左往右找，到每个位置要使得 $a_i-u+(a_t-c+1-u)\leq c$，$u$ 指截至目前用过的次数

贪心地，每次选择右端点最右的可行的区间，包含之前用剩的

费用提前计算并不精确。但是明显地，是正确的

ZR20day16A

每次选择最小的一个团，加点就好了

ZR20day16B

根据LGV，答案为
$$
\begin{bmatrix}
\binom{a_1+1}{1}&\binom{a_1+2}{2}&\cdots&\binom{a_1+n}{n}\
\binom{a_2+1}{1}&\binom{a_2+2}{2}&\cdots&\binom{a_2+n}{n}\
\vdots&\vdots&&\vdots\
\binom{a_n+1}{1}&\binom{a_n+2}{2}&\cdots&\binom{a_n+n}{n}\
\end{bmatrix}
$$
的行列式

每列提取出 $\frac{1}{j!}$

变成上升幂的形式

可以通过初等行变换变成普通幂的形式

也就是变成了范德蒙德行列式

直接带式子就行了：
$$
\prod_{i=1}^n\frac{1}{i!}\prod_{i=1}^na_i\prod_{1\leq i<j\leq n}(a_j-a_i)
$$
后面的prod直接ntt

11.17

ZR20day15D

首先可以n^4DP

然后发现可以n^3

但是一般的n^3DP不太好优化

这需要发现另一种DP的方式，即枚举从 $x,y$，更新 $f_{x,i}\rightarrow f_{y,j}$

这样每次做是n的

然后考虑CDQ分治

具体的做法就是将[l,mid]和(mid,r]的中间线脑补成一行

就能把左边转移到它，再把它转移到右边所有

每一层是len^2的

分析下来n^2log

ZR10day9D

对于 $\frac{x}{x+c_i}$，可以化简成 $\frac{1}{1+\frac{c_i}{x}}$

看到求一个 $Cx^{-1}$ 的式子，就应该有对泰勒展开的敏感

当 $x<c_i$ 时，

2021.12

12.2

LUOGU4027 货币兑换

是CDQ维护斜率优化的裸题

但是很久没有写斜率优化了，导致卡了许久

这里规范一下写法：

使用斜率进行实数比较，比较时统一使用$<$ 或 $>$
求斜率时，特殊处理 $x_1=x_2$ 的情况，若 $y_1<y_2$ 输出 $+\infty$，否则输出 $-\infty$

LUOGU4585 火星商店问题

首先应该能想到线段树分治，但是由于在时间维度上，修改为单点，询问为区间，所以不能直接做

于是把每个修改挂在时间线段树上的节点上，并考虑如何贡献

然后考虑在每个节点建立主席01trie，就能应对查询了，时间复杂度为 $O(n\log^2n)$

这里就体现出了线段树分治对有类似 $[l,r]$ 这样区间限制的贡献问题的优越性，若是使用高级数据结构就太难写，交给cdq处理就要多一个log

12.5

ARC131C

首先如果S在集合里面，那么就一定是先手胜

否则讨论集合大小是奇数还是偶数：

奇数：

首先，游戏明显不会在2步时结束，否则他就不会是奇数

然后，把这两步去掉，就变成了一个奇数的子问题，如此递归，一定是最后剩一个数，所以先手胜

偶数：

首先，游戏有可能在2步时结束

若结束了，则后手胜

若未结束，则递归进子问题

子问题的终点是后手拿光了所有的数，也是后手胜

ARC131E

把它看成一个邻接矩阵，一个三元环就相当于一个直角三角形的三个顶点

那么考虑对一行一列来考虑，其集合的情况有以下两种：

大小分别各不超过2，且两集合是包含关系
一个大小不超过3，另一个大小为1

对于第一行来说，如果是第一种情况，那么所有的列最多也就何其相同，那么另一种颜色就一定访问不到，所以1这种情况排除；

如果是第二种情况，考虑所有行的大小都是1，那么很显然就没有列的限制了，就变得水水水水水

对每种颜色分配行，就做完力！芜湖

12.20

ABC232F

考虑先swap后增减，则可以构造一个排列 $P$ 使得答案为
$$
X\cdot\sum_{i=1}^n|A_{P_i}-B_i|+Y\cdot \text{inv}(P)\
=\sum_{i=1}^nX\cdot |A_{P_i}-B_i|+Y\cdot#{x\in P_{[1,i)},x>P_i}
$$
右边的井号部分只和已选元素的集合有关，所以可以状压DP，时间复杂度为 $O(n^22^n)$。

ABC232G

可以使用dijkstra算法，但是由于边数为 $O(n^2)$，故不满足时间限制。

由于 $(A+B)~~\text{mod}~~M=(B-(-A))~~\text{mod}~~M$，而两数之差在模意义下为两数顺时针移动的步数，因此可以离散化以后建出值域点，值域点之间按从小到大连边（同时最大点连向最小点），即可简化图内信息。

12.22

CF1100F

有两种做法

Sol.1

固定右端点，那么随着左端点向左扩展，线性基最多只会变化 $\lfloor\log V\rfloor$ 次，所以每次把 $a[r]$ 插入这些线性基中，总时间复杂度为 $O(n\log^2 V)$（记录下来，可以在线！）。

Sol.2

如果可以在右端点向右推进时维护一个全局的线性基，使得当前的询问均可在其中查询就好了。

思考线性基求 $\max$ 的实质：从高到低位遍历，如果当前答案的该位为0且线性基的该位有值，则将答案异或该值。

考虑在线性基中对每个值维护一个下标 $pos_i$。如果 $l\leq pos_i$，则可以扔进去。

这样做的要求是 $pos_i$ 尽可能大。由于每个数只能在线性基中插入一位，而每次都要贪心地选择最高位插入，所以线性基插入时需要 swap 当前值和记录值，以保证这一位的 $pos_i$ 最大。

总时间复杂度为 $O(n\log V)$（记录下来，可以在线）。

2022.1

1.4

P2303 [SDOI2012] Longge 的问题

式子：
$$
\sum_{i=1}^{n}\gcd(i,n)=\sum_{d|d}\sum_{i=1}^{n} d[d=gcd(i,n)]\
=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\
=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j|i\and j|\frac{n}{d}}\mu(j)\
=\sum_{d|n}d\sum_{j|\frac{n}{d}}\mu(j)\frac{n}{dj}\
=n\sum_{d|n}\sum_{j|\frac{n}{d}}\frac{\mu(j)}{j}\
=\sum_{j|n}(n/j)d(n/j)\mu(j)
$$
理论上没有什么问题，但是可以用欧拉函数：
$$
\sum_{i=1}^{n}\gcd(i,n)=\sum_{d|d}\sum_{i=1}^{n} d[d=gcd(i,n)]\
=\sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\
=\sum_{d|n}d\phi(d)
$$
基础不扎实（摊手）

CF1334E Divisor Paths

基础不扎实（摊手）

首先考虑成倍数的情况，那么一定是直直的走过去，所以答案为算gcd的素因子的可重集

那么如果是任意数的话，一定是先向下走，再向上走

那么就算x->gcd->y就好了

P3868 [TJOI2009] 猜数字

差点都忘了CRT怎么写了

首先就是类似于拉格朗日插值，构造值 $v_i$ 使得除了膜 $b_i$ 为 $a_i$，其他都是0

然后加起来就行

excrt再说吧

P3312 [SDOI2014]数表

$$
a_{i,j}=\sum_{d|gcd(i,j)}d\
\
\sum_{i=1}^n\sum_{j=1}^mv_{gcd(i,j)}\sum_{d|gcd(i,j)}d\
…\
=\sum_{x=1}^n\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\sum_{d|x}\sigma_1(d)\mu(\frac{x}{d})
$$

正常来说，可以很简单地求，但是sigma_1会变

涉及到修改和询问，需要结合数据结构，设后面的sum为 $s(x)$，则只要维护好 $s(x)$，就能轻松求值

如果按正常顺序做，修改操作的数量过多，所以考虑预处理或离线，这里用离线做（离线显然好写）

那么按sigma_1排序就会发现每次操作即使为 $s(x)$ 新增一项，而 $s(x)$ 的个数是调和log的

所以这么做就好做了，时间复杂度为 $O(n\log^2n+q\sqrt n)$

1.5

P3327 [SDOI2015]约数个数和

$$
\sum_{i=1}^{n}\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\
\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum_{d|\gcd(x,y)}\mu(d)\
\sum_{d=1}^m\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dy}\rfloor
$$

难点在第一步。因为转换枚举顺序发现无法维护，于是考虑替换 $d(ij)$。朴素的想法是枚举 $x,y$ 分别整除 $i,j$，但是会算重，于是规定只有 $gcd(i,j/y)=1$ 时才贡献，就有了最开始的式子。

在第二步时总是会多余地引进 $g$ 来表示gcd，但是这是多余的。

P5330 [SNOI2019]数论

$$
x\equiv a\pmod p\
x\equiv b\pmod q\
k_1p+a=k_2q+b\
k_1p-k_2q=b-a\
\Rightarrow k’_1p-k’_2q=\gcd(p,q)\
$$

但是没啥用，因为对于末尾难以分析。

可以换种思路，考虑对 $a_i$ 求可行的 $x,px+a_i\equiv b_j\pmod q$。

在固定 $a_i$ 时，不断 $i++$ 会形成一个环。

对每个 $a_i$，在这个环跳，对每个点做记录就好了。

（所以最后为啥变成了图论题）

写完一块代码，记得检查该清空的是否清空哦~

1.6

P5323 [BJOI2019]光线

设 $f_i,g_i$ 分别表示从这块玻璃向后射的光线量，向前射的光线量

那么可以列出式子：
$$
\begin{cases}
a_{i}f_{i}+b_ig_{i}=f_{i+1}\
b_if_{i}+a_ig_{i}=g_{i-1}
\end{cases}
$$
当 $i=n$ 时，有
$$
\begin{cases}
a_nf_n=f_{n+1}\
b_nf_n=g_{n-1}
\end{cases}
$$
答案是 $f_{n+1}$。根据上两式，所有的 $f_i,g_i$ 都能用 $f_{n+1}$，反带到 $f_1=1$ 即可

1.7

P4589 [TJOI2018]智力竞赛

使用二分答案让问题变成选择固定的某些点。

这个问题可以费用流。

但是显然不用这么麻烦，因为转化一下问题就变成了寻找图上的链覆盖，然后裸着做就好了。

虽然板子是说DAG，但是有环图上不经过重复点的链覆盖也能做。

1.10

CF888G Xor-MST

首先就能想到B算法。

但是直接运用比较麻烦，考虑简化。

注意到查询连通块之间的答案时，可以运用字典树，如果能启发式合并的话时间复杂度可以接受，于是继续寻找性质，使得字典树和B算法可以很好的结合。

从高位到低位处理时，可以发现合并相邻两个子树是最优的。

于是就这么做了，还不用可持久化。

1.11

deleted

1.12

deleted

CF1625D

建出全局trie树，发现如果某个子树的深度>某个值D的话，两个子树的集合就能简单合并，<D的话，就无法合并，=D的话，就可以把左子树的值在右子树中查询，判断这个子树是选一个数还是两个数。

思路比较简单，但是不好写。

1.13

CF1625E

对于一个合法的括号序列，可以建出一棵树来表示其结构（树上的每个点表示一个括号对）。

每一个询问在一棵树上的表示一定是同一层上的连续节点。

每一个修改在一棵树上的表示即为删除一个叶子结点，并将祖先都减去同一个数。

所以可以 $O(n\sqrt{n\log n})$ 操作分块。

（未完待续）

由于节点DFS序与BFS序无关且混乱，所以考虑查询的时候查询子树。

因为每次更新都是在根到某点的链上减去同一个常数，所以将权值与深度结合可解。

1.14

deleted

P4768 [NOI2018] 归程

先跑个单源最短路，再建出kruskal重构树，直接做出来了。

P5633 最小度限制生成tree

很显然的一个wqs二分的限制，直接做wqs二分，与s相连的边都+=c。

P1484 种树

固然可以反悔贪心，但也能花哨地wqs二分。

正常地wqs二分就好了，斜率一定是为整数。

由于求的是<=k的最大值，所以可以把斜率下界设为1。

1.15

deleted

1.16

deleted

前记

最近总感觉没什么动力，且正逢我练习打字的时段，于是打算把所谓好题集给刷穿。

（校注：孩子你想多了）

P4747 [CERC2017]Intrinsic Interval

根据这样的区间满足 $mx-mn=r-l$，即 $mx-mn-l=r$ 的结论，因此在固定右端点的情况下，可以知道每个左端点的答案。

这里用线段树维护。

然后从左到右扫，遇到右端点把左端点加入大根堆，每次把可行的拎出来就好。这样一定是对的因为如果存在 $[l_1,r_1],[l_2,r_2],l_1<l_2,r_1<r_2$ 都满足要求，则 $[l_2,r_1]$ 也一定满足。

Tags

Archives

Recent Posts

2021.7

6.29（把前几天的补一下orz）

关于博弈问题

字典序第k小

高级数据结构（一）

关于水题（一）&关于比较乱x的题

关于毒瘤题（一）

关于字符串（一）

关于计算几何

关于BSGS

关于组合题

复杂度的结论

高级数据结构（二）

6.30

网络流

图论问题（一）

奇怪的树形DP

奇怪的数学题

7.1

数论和矩阵

something else

DP（一）

字符串（二）

关于图论模型

7.2

一些看着很计数又很集合的题

7.16

N2O5-A

N2O5-B

N2O5-C

N2O6-A

N2O6-B

N2O6-C

7.17

N2O9-A

ABC210E

ABC210F

7.18

N2O9-B

N2O9-C

多项式

FFT（扶扶她）

NTT（脑瘫瘫）

分治FFT

多项式求逆&多项式开根&多项式除法&多项式取模

多项式多点求值

快速（龟速）插值

7.19

N2O7-A

N207-B

N2O7-C

数论复习（上）

辗转相除法

辗转相减法

同余

裴蜀定理

乘法逆元

欧拉定理

扩展欧几里得算法

中国剩余定理（拉格朗日插值）

扩展中国剩余定理

阶

原根

BSGS

米勒·拉宾

泼辣的·肉

7.20

N2O8-B

N2O8-C

数论复习（下）

积性函数

狄利克雷卷积

莫比乌斯反演

线性筛

数论分块

杜教筛

burnside引理/polya定理

2018雅礼方阵