SNOIP-听课简记

本文仅为笔记的简略部分，其中一些较为完整的已独立成文， 请移步至对应文章。

Day1

1.4089: 大嘴乌鸦

桶，前缀和，位运算

---

我们要找k%(sum[r]^sum[l-1])==0，我们可以先把k的因子记录一遍，存到v数组中，然后枚举这个因子v[j]，那么就是找sum[r]^sum[l-1]==v[j]，根据异或的性质，那么就是sum[l-1]==v[j]^sum[r]，因此我们只需要找到这个l的前缀异或和出现的次数就可以了。

而每经过一个点，就把它对应的前缀异或和出现的次数加一。

一个数的因子最多大概是$\sqrt(n)$个，因此复杂度是$O(n\sqrt(n))$。

2.4090: 艾莎

线段树

---

只需要维护长度为2和3的最大子段，

线段树维护区间内所有长度为2的连续子段中最大和区间内所有长度为3的连续子段中最大。

因为任意一个区间都可以被分成两段不同的区间，这两个区间的平均值一定有一个大于等于原来的区间，另一个区间的平均值小于等于原来的平均值，所以这么不断去下去，直到剩下三个，那么假如分出来的那一个点比原来的大，但是剩下的两个比原来的小，由于一个点不能独立为一个区间，因此要保留三个。

合并的时候分两种情况讨论，

区间加的时候就分别两倍三倍加。

我们每个区间记录一下左端的两个值和右端的两个值，合并的时候比较一下原来两个区间的最大值和交界处新产生的值比较一下取最大就可以了。

3.4091: 沙奈朵

分块

---

首先题意是要找一定范围内的每一个小区间，每个小区间的答案是这段区间内不同的值的个数（色块数，同一个数为一个色块，色块数的前缀和需要预处理方便区间查询），然后求这些区间答案的和。

采用分块的思想

把序列分成根号个块，每个块长度大概为$\sqrt(n)$

维护一个$a$代表$i$之前的每个$1$到$i$这个位置的染色段数

用A[x]代表当前位置向左所有答案累积和（类似于前缀和一样的东西）。

用B[x]代表当前位置向右产生所有答案的累计和

用C[x]代表当前块的x的个数

用D[x]代表当前块的答案

当前位置向左累计产生的答案为红色段加和。

每遇到一个$x$就需要将其A累加到当前块的总答案中，

每个颜色其实就是$a$的一种状态，

那么怎么转移呢？

算出两个相邻的x之间的答案再乘以之前出现x的次数，累加到A上

正着把这个区间枚举一遍得到A的值和当前块总共的答案，

合并块的时候，左边的块对于右边会产生答案，右边的块对于左边会产生答案，

查询的时候（临时变量ans）：

ans+=l.A[x]*r.C[x]+r.B[x]*l.C[x]+l.C[x]*r.C[x]*(!l.r==r.l)

new.A=l.A+r.A*l.C

如果遇到单点修改，那么就重置一下当前块，复杂度为sqrt(n)，

一开始需要把每个块扫一遍，把每个A,B,C,D都预处理一遍，还要预处理一个区间不同色块数的前缀和，因为从这个点到上一个点产生的答案即为这段区间内色块数，$O(1)$查询

4.4092: 绒绒鸹

树链剖分，DFS序

树链剖分：

dfs序可以保证对任何一个点的子树都是序列中的一段区间。

重儿子：子树大小最大的儿子

重链上每取一个区间都是在dfs序上一段连续的区间

往上跳一次轻边至少会翻倍

那么路径最多就可以通过$log$个区间连接起来

维护一下当前位置的i还要跳几步才会跳到重链头

用小根堆维护f的最小值，再开个全局标记。

习题

DFS序

Day2

1.

none

---

太简单了没啥好说的

2.

DP，树状数组

求长度为$k+1$的最长上升子序列的方案数。

$f_i$代表以$i$为结尾的最长上升子序列，

$i$的值可以由$j$的状态转移过来。

那么我们可以令$f_{i,j}$表示以$i$结尾长度为$j$的最长上升子序列的方案数。

那么如果一个$y$的位置长度为$j$可以被更新，那么它的上一个位置$x$长度为$j-1$可以更新它，也就是累加上$x$的答案。

因此要更新需要满足的条件是$a[y]>a[x]$，更新给$f_x$ 的值就是所有满足这个条件的$y$的和。

即图中所有的$x$的$f$值都需要累加。

那么我们可以开一个二元组来维护这个关系，

$(a_i,f_i)$

这样其实就是在找$a_i$左边的所有的$f_j$的和。

怎么保证$j<i$？

是从前往后插入的。

用树状数组优化区间求和问题。

由于$k=11$，因此需要开$11$个树状数组来维护这个问题。

每次更新第$j$层时，需要访问第$j-1$层树状数组。

3.

树上倍增，树上区间

---

$i$表示最后一个选择的区间的右端点，

$f_i$表示最多能选的区间，优先选短的区间，

对i而言，找到一个最大的j使得区间和为0，即右端点和左端点左边的前缀和相同

记录一个last为上次和i前置和相同的点的位置，

i一定从j-1转移过来么？

不一定，因为上一段不一定以j-1结尾

那就把j之前的区间的f值取个max来更新$f_i$

$f_i=max(f_j)+1$

那么q次询问就需要通过数据结构来优化复杂度

以每个i结尾的区间最多只有一个有意义，即最小的，

那么总共就有n个区间有意义，将它预处理出来，然后建树

以i结尾的区间for一遍就可以通过last维护最小的这个区间

选完一个区间后就可以选右端点最小的区间

所以说选完以后选下一个区间是一个固定的过程

预处理

这样出来以后就是一棵树

第一个的是左端点大于l右端点最小的区间

然后一直走直到超出r

倍增求解就可以了

T22526 Princess Principal

树上倍增，树上区间

---

从左端开始不断选最长的区间

从左端不断连边

那就从左边开始不断跳，这样就可以倍增处理了

4.

平衡树，区间求和

不能枚举区间

i为分界点

以i开始的前缀和以i结束的后缀区间

两两组合成的区间，

左边对应最大前缀，

右边对应最大后缀，

只需要把左边的所有最大前缀和右边的最大后缀的和乘起来

求的时候就需要从前往后枚举一遍，边求前缀和边取max

维护一个集合S

S中：维护当前区间除去最大前缀的和

那么这个东西大于0就需要更新

那么i变为i+1后，每个元素都$+=a[i+1]$

第二个操作：

找出所有x，y>0

修改为x+y,0

每次插入则修改全局标记

插入的数要减去当前的tag

tag要加上当前插入的数

一开始它们的最大前缀是不一样的

只要后缀被更新一次，那么就不会再不同，那么就可以合并区间

合并以后y的和就可以知道了，

其实就开一个临时变量，然后扫的过程中把最大前缀和的总和记录下来就可以了

记录一下已经合并的区间的数量

这样正着扫一遍，倒着扫一遍，然后两个乘起来就可以了

P2344

树状数组，DP

设$f_i$表示$1$到$i$的前缀划分成若干个子区间使它$\ge0$

前面有个$j$使得$f_j\ge0$

也就是$pre_i-pre_{j-1}\ge{0}$

$pre_{j-1}\le{pre_i}$

的$f_{j-1}$的和。

那就和上面T2类似了，树状数组维护一个二元组$(pre_{i},f_{i})$求满足上述条件的$f_{j-1}$的和。

P1725

DP+单调队列优化

P3572

飞到i最小的代价为$f_i$

一个点可以到一个区间

我们倒过来，其实就是从一个区间中飞过来

可以用单调队列维护dp最小值

以dp值最小为第一关键字，树的高度最大为第二关键字，维护这样一个

假如dp值一样，那么高度越高越优

假如dp值不同，那么dp值越小越优（相对于n的dp值）

P5658

树

$f_i$代表从i到根有多少合法的子串

是由它父亲转移来的

比它父亲就多了个点，也就是多出了所有以i为结束点的子区间

$g_i$代表以i结尾的到根的合法区间的个数。

假如是（，那么就是0

假如是）

假如j和i这段区间构成匹配的括号串

$g_i$=$g_{j-1}+1$

那么我们i的dp值就等于j父亲的dp值+1

我们要维护一个栈使得它dfs的时候和回溯的时候的状态相同

因为匹配的时候我们会弹出两个括号，会导致多弹出，需要记录，回溯的时候再插入

Day3

1.开关

BFS广搜

$s^{16}\times{16}$

2.

最小生成树

---

不需要选出来$sum$

加的时候注意一下有没有超过x就可以了

不需要算出来，

3.

最短路

4.

匈牙利算法

---

点权从大到小排序

贪心选

其它

新矩阵乘法

$C_{i,j}=A^k$

其实就是限制了边数的Floyed，k为边数

$C_{i,j}=\min(A_{i,k}+B_{k,j})$

令点双为方点，其他为圆点，然后在它们之间连边，那么最终得到的一定是个树

---

我的拓扑

缩点

点双 边双

树上差分

圆方树

哈密顿路

竞赛图

DP

DAGDP

Day4

1.

DFS

2.

顺着边 点编号是递减的

从点i右边跳到i号点的概率永远是$\frac{1}{i}$，所以在所有点中病毒的情况下，让他们排成一条链的概率就是

给定一个$1\sim{n}$的子集$S$，询问若$i$的父亲在$[1,i-1]$中等概率生成，那么从最后一个点到一号点经过所有$S$中的节点的概率，答案对$998244353$取模。

首先，$i+1$到$i$的概率是$\frac{1}{i}$，$i+1$的父亲是$i$的概率是$\frac{1}{i}$；

$i+2$到$i$的概率是直接跳到$i$的概率加上先跳到$i+1$再跳到$i$，也就是 $\frac{1}{i+1}+\frac{1}{i+1}\times{\frac{1}{i}}=\frac{1}{i}$，通过数学归纳法得知，$i$右边的点跳到$i$的概率都是$\frac{1}{i}$。

由于每次跳这些时间是相互独立的，所以原题答案为：

$\prod_{i=1}^{m-1}{\frac{1}{x_i}}$

最后一个分数取模不要忘了求逆元。

3.

题意：对于一个无向图，让你给定每条边方向，使得每个节点的入度为偶数。

首先，士兵人数一定要是偶数，否则不管怎么分配也一定无法分全。

也就是边的数量为偶数。

对于一颗树，叶子节点是绝对不能去的，因为这样不可能是偶数。那就从叶子节点开始，士兵向上走，如果当前点士兵数是奇数，那就让它上面的边的士兵向下走到这个点，否则就向上走。

这样就可以维护所有非根的点的士兵数都为偶数，由于士兵总数为偶数，那么根节点最后也一定是偶数。

但是这样一张无向图不一定是树，所以我们可以建一颗 DFS 树，无向图中， DFS 生成树仅存在树边和回边，所以对于每个回边，我们让它回到深度更大的点，剩下的就和树上是一模一样的了。

4.

有一些从右向左扫的激光炮，假如打到了防护罩，那么这个激光炮就会失效。

对于第$i$个设备，我们定义$r_i=\min_{i\in{[l_j,r_j]}}(r_j)$，也就是能打到第$i$号点的激光炮中右端点最小的$r$，那么我们在这里放一个防护罩就一定可以保护$i$不受攻击。

而在$[i,r_i]$中选取一个$j$，那么$r_j\le{r_i}$，这是因为$r_i$是一定覆盖$j$的，若没有比这个还小的$r_j$，那么$r_j=r_i$，否则$r_j$就会比$r_i$更小。

而对于$j>r_i$，那么$r_j>r_i$，因此我们可以得出：所有的区间要么互相包含，要么无交，所以就可以根据这样的关系建一颗树：

在树上进行以点权和为标准的长链剖分，假如一条路径上放了一个防护罩，那么这条路径就是安全的，因为装置在区间的最左端，这样每次贪心地选$k$个长链就可以使保护的权值和最大，从而使破坏的权值和最小。

树上差分

一条路径，对于叶子节点+1，终点的父亲节点-1，求和只需要求终点的子树和就可以了。

LCA小技巧

比如要求黑色点$u$和粉色点$v$的$lca$的深度，那么就可以把从$u$到根的路径上的点权都加一，然后求$v$到根的路径上点权的和。（初始点权都是0）

那么对于$\sum_{i\in{S}}dep_{lca(i,z)}$，我们就可以每次把$i$到根路径上的节点点权加一，最后统计$z$到根节点路径点权和，这样就可以把所有$lca$的深度和求解出来。

而对于$\sum_{i=l}^r{dep_{lca(i,z)}}$就可以通过前缀和$\sum_{i=1}^{r}dep_{lca{(i,z)}}-\sum_{i=1}^{l-1}dep_{lca_{(i,z)}}$求解。

长链剖分

长边组成长链，

至少能查$len$级祖先，$len$为该长链长度，

一个长链肯定能跳到下一个长度和它相同的下一段长链。

那么假如$k\le{len}$那么就可以很轻易地查询$k$级祖先，

类似ST的预处理，我们令$p=\lfloor{log_j}\rfloor$，那么我们先跳$2^p$步，再跳$k-w^p$步，那么就可以跳到了。

假如第二次跳出了当前的长链，没关系，还可以跳到下一条长度同样为$len$的长链的段，这样就可以查到了。

树的重心

所有点到这个点的距离之和最小，那么这个点就是重心。

树的重心就是从上往下遍历找到的最深的满足子树点权和$\ge{\frac{\sum_{i}d_i}{2}}$的点。

那我们把这棵树给序列化，枚举它的前缀区间，直到找到第一个右端点$r$使得$\sum[1,r]\ge{\frac{\sum_{i}d_i}{2}}$，那么现在就有两种情况，第一种就是这个点在重心的子树中，第二种是它不在重心的子树中。假如它不在重心的子树中，那么中心的子树要么在左边的区间，但显然不可能，因为在$r$之前的区间都不满足$\ge{\frac{\sum_{i}d_i}{2}}$的条件，那就只可能是在后面的区间，后面的区间那就从一个非零的点开始找了，否则就找刚才加入的最后一个点（即满足条件的最小的$r$）。

Day5

1.

令$f_{i,j,k,0/1}$表示走到$(i,j)$异或和为$k$且还剩$0/1$颗珍珠的方案数。

递推式为：

$f_{i,j,k,0}=f_{i-1,j,k,1}+f_{i,j-1,k,1}+f_{i-1,j,k\oplus{a_{i,j}},0}+f_{i,j-1,{k\oplus{a_{i,j}}},0}$

$f_{i,j,k,1}=f_{i-1,j,{k\oplus{a_{i,j}}},1}+f_{i,j-1,{k\oplus{a_{i,j}}},1}$

最后答案就是$\sum_{k=1}^{127}f_{n,m,k,0}\times{k}$。

2.

定义$f_i$是从以$i$为根的子树中选出单调递减的路径的方案数，$g_i$是从以$i$为根的子树中选出单调递增的路径的方案数。

对于每个节点一开始$f,g$值都为$1$，因为它们还没有假如任何其它节点，只能选自己的方案数为$1$。然后开始$dfs$，在回溯的时候处理$f_i+=\sum_{i>k}f_k,g_i+=\sum_{i<k}g_k$，$k$在$i$的子树内。

递归的时候选取一个点作为要选的两个点的 LCA ，然后选取离这个点最近的两个点设为$x,y$，那么我们就需要首先合并$x$和$lca$，也就是更新$lca$的信息（$f,g$），然后合并完之后这就是一个新的集合，那么就可以把它和以$y$为根的子树进行合并，合并的时候分别枚举两个集合中的点$i,j$，假如$i<j$，那么答案累加就是$ans+=f_x\times{g_y}$，因为是$i\to{j}$的一条路径，所以$i$到$x$是单调递减的。相反地，如果$i>j$，那么就是$ans+=f_y\times{g_x}$。

先合并 lca 和它的第一个子树，也就是目前知道$1$子树的信息以及根节点$0$当前的信息，很显然$1$没有其它子树，它的信息不会再被更新，而$0$还是有其它子树的，也就是说它的$f,g$仅限于当前遍历到的子树，即$1$。

那么我们再枚举其它子树，实际上就是不断合并连通块更新信息的同时并累加答案。

这样全部合并完后，$ans$就是答案。

3.

数位 DP

---

首先题意是让你找出所有的序列，这个序列满足长度为$n$序列和等于$m$，序列中的每个数都满足$\in{[0,m]}$的范围，该序列的价值为该序列中所有的数的异或和，答案是所有情况的异或和的求和$\pmod{1e9+9}$。

我们可以来看序列中$n$个数和$m$的二进制表示，定义$f_{i,j}$为考虑完前$i$位，且第$i$位的和等于$m$的这一位，下一位进位为$j$的方案数，$g_{i,j}$表示考虑完前$i$位，且第$i$位的和等于$m$的这一位，下一位进位位$j$的所有方案异或和的求和。

因为我们要保证序列和为$m$，所以我们要保证二进制下每一位加起来都等于$m$的这一位。

然后我们枚举一个$k$代表第$i$位我要在$1\sim{n}$中填多少个1。

那么$f_{i+1,{\lfloor\frac{j+k}{2}}\rfloor}=f_{i,j}\times{C(^{n}_{k})}$，其中$C$为组合数，意为原来的方案数，在$i$这位又产生了$C(^{n}{k})$种可能，由于相互独立性，因此下一位的方案数是它们相乘。

假如$k$是偶数，那么这一位异或起来一定是$0$，所以不会产生新的贡献，有的只是新的情况，所以就相当于有若干个$g_{i,j}$加了起来组成了新的状态，也就是：

$g_{i+1,{\lfloor\frac{j+k}{2}}\rfloor}=g_{i,j}\times{C(^{n}_{k})}$

假如$k$是奇数，那么这一位异或起来一定是$1$，而第$i+1$位加一，产生的贡献是$2^{i+1}$，所以会产生情况数$\times$每种情况的贡献，也就是：

$g_{i+1,{\lfloor\frac{j+k}{2}\rfloor}}=g_{i,j}+2^{i+1}\times{f_{i,j}}\times{C(^n_k)}$

所以最后的答案就是$g_{logm,0}$。

4.

类似地，每个人会去能去的档次最高的店，定义$f_{i,j}$为只考虑$[i,j]$这个区间里的人所能得到的最大收益是什么，枚举标准最高的店$k$，定义$g_{k,t}$为有$t$人到第$k$家店，$t$为能到达$k$的人数，那么$f_{i,j}=f_{i,k-1}+f_{k+1,j}+g_{k,t}$。

$g$表示合理选择第$k$家店的档次使得收益最大的收益。

$t=S_{i,j}-S_{i,k-1}-S_{k+1,j}$

接下来就是求出所有的$g_{k,t}$，用$c_i$表示$i$的花费，$h_j$代表有$j$个人来的最高收益，也就是$g_{k,j}$。

$h_j=max(i\times{j}-c_i)$，

$i_1<i_2$

$i_1\times{j-c_{i_1}}$

$i_2\times{j-c_{i_2}}$

2比1优的时候，往后2都会比1优，由于2的斜率比1斜率大，交点之后2更优

假如$i_1\times{j_1}-c_1\ge{i_2\times{j_2}-c_2}$

这样处理完之后函数的斜率是单调递增的，

往后优解不一定是连续的，优先选斜率大的。

所以维护的是所有可能成为最优解的斜线，被覆盖的没必要维护（覆盖可以通过函数图像的交点位置来判断），维护可以用单调栈。

最后处理出来就是一个永远最优的分段函数。

快乐

定义$S_{i,j}$为完全包含在$[i,j]$区间内的线段的个数(人数)，这样就可以线性求完全包含在$[i,j]$内并且包含我枚举的$k\in[i,j]$的一个区间，也就是$S_{i,j}-S_{i,k-1}-S_{k+1,j}$ ,$k$为我枚举的假设最大值，让这些能到$k$的区间都到$k$，然后求一下这段区间。

凌乱

如何选择一种切法使得这个矩阵凌乱度最小

$f_{1,1,i,m}\le{f_{1,1,i+1,m}}$，

也就是说是单调不降的，

所以最大就是

$g_{i,j,k,l}=x$左上角$(i,j)$，右上角$(i,k)$，最大的数满足$f_{i,j,x,k}\le{l}$（左上角右下角，矩阵凌乱度$\le{l}$，

假如横着切，上下两个矩阵都小于等于l-1

$g_{i,j,k,l-1}=y$

下面

$g_{y+1,j,k,l-1}=x$

$g_{i,j,k,l}=g_{g_{i,j,k,{l-1}}+1,j,k,{l-1}}$

竖着切：

$g_{i,j,k,l}=max(y),y=min(g_{i,j,y,l-1},g_{i+1,y+1,k,l-1})$

因为就要切在下边界较小的那一个矩阵，因此要取min

$h_y=min(g_{i,j,y,l-1},g_{i+1,y+1,k,l-1})$

$h_y$是先增后减的。

$g_{i,j,k,l}\ge{g_{i,j,k+1,l}}$

相当于面积相同的情况下，宽越大，高越长。

在中间竖着切了一刀，左边随着宽不断增大，高是不断减小的，右边相反，

所以$h_y$的第一项是单调不增的，第二项是单调不减的，

加上一个取min操作，将会存在一个分界点，使得其图像为一个单峰函数，

设分界点为$z$，$z$左侧第一项大于等于第二项，$z$右侧第一项小于等于第二项

因此$h_y$是先增后减的，可以通过二分查找这个分界线，然后比较它上面和下面的值谁更大。

$O(N=n^3logn\times{logn})$

P9387

$4k\oplus{4k+1}\oplus{4k+2}\oplus{4k+3}=0$

这样就可以快速处理出$x$的值。

我们设$f_{i,j,k=0/1,t=0/1}$表示我考虑了二进制的前$i$位$(0\sim{i})$，当前位将向下进位的值是$j,j\in{0\sim{n}}$，$k$表示$b$是否大于$0$：$true/false$，$t$表示前$i$位是否大于$n$，此时的方案数。

（$b$大于或等于$0$）

那就可以从低位到高位进行 DP 了，初始时$f_{-1,0,0,0}=1$

转移方程是：

$f_{i+1,y,O_b|t,0/1}+=f_{i,j,t,k}$

这里$y=\lfloor\frac{O_a+O_b+O_c+j}{2}\rfloor$。

$O_x$代表$x$的当前这一位的值，由于要满足$(a+b+c)\oplus{a}\oplus{c}=x$，因此设$z={O_a+O_b+O_c}\pmod{2}$，$z\oplus{O_a}\oplus{O_c}=O_x$。而这位的$O_a,O_b,O_c$分别枚举一下就好了，选出符合这个条件的进行转移。

$n$个二进制数加起来最多进$n-1$位，三个数最多进$2$位。

至于$\le{n}$，假如下一位小于$n$的下一位，那么就是小于
$n$，为$0$，假如下一位和$n$相同，那就继承上一个状态，因为还要接着比下去，如果下一位比$n$大，那就是大于，为$1$。

最后的答案就是$f_{60,0,1,0}$，因为$1e18$的二进制位数不会超过$60$位。

Day6

1.

2.

3.

4.

卢卡斯定理

对于$n,m$和质数$p$，有$C(^n_m)\equiv{C(^{\lfloor\frac{n}{p}\rfloor}_{\lfloor\frac{m}{p}\rfloor})C(^{n\%p}_{m\%p})}$

$p=2$时，$C(n,m)=1,n\ge{m}$，所以$m$第$i$位为1时，$n$的第$i$位为1，$m$的第$i$位为$0$时，$n$的第$i$位为$0/1$，所以$n\&m=1$。

欧拉函数

$\phi(n)=\prod^{t}_{i=1}(p_i-1)p_i^{a_i-1}=n\cdot (1-\frac 1 {p_1})(1-\frac 1 {p_2})(1-\frac 1 {p_3})\dots(1-\frac 1 {p_t})$

$n=p_1^{a_1}p_2^{a_2}\dots{p_t^{a_t}}$

$1-\frac{1}{p_1}=\frac{p_1-1}{p_1}$

相乘即得。

P2261余数求和

对于$n\in[1,1e7]$，求$ans_n=\sum_{i=1}^n{n}\mod{i}$。

来求解一下递推式：

$ans_n-ans_{n-1}=\sum^{n-1}_{i=1}{n}\bmod{i}-\sum_{i=1}^{n-1}{n-1}\bmod{i}$。

这里第一项之所以枚举到$n-1$是因为枚举到$n$会使$n\bmod{n}=0$所以就省掉了。

接着化简：

$\begin{aligned} ans_n-ans_{n-1}&=\sum^{n-1}_{i=1}{n}\bmod{i}-\sum_{i=1}^{n-1}{n-1}\bmod{i}\\ &=\sum_{i=1}^{n-1}[(n\%{i})-(n-1)\%{i}]\\ &=n-1-\sum_{i=1}^{n-1}i\times[n\%{i}=0]\\ &=2n-1-\sum_{i=1}^{n}i\times[n\%{i}=0]\\ &=2n-1-\sigma_k(n)\\ \\ \therefore ans_n&=ans_{n-1}+2n-1-\sigma_k(n) \end{aligned}$

然后就可以线性递推了。

原T4

求 $f_i=\sum_{j=0}^{m}j^i$

那么我们先求一下 $\sum_{j=0}^m(j+1)^i$

那么这个是什么呢？

实际上是 $f_i-0^i+(m+1)^i$

因为这样实际上是枚举了 $1-m+1$

相当在原来的枚举基础上少枚举了 $0$ 但是多枚举了 $m+1$

那我们接着往下处理这个式子

$\begin{aligned} &f_i-0^i+(m+1)^i\\ &=\sum_{j=0}^m(j+1)^i \\ &=\sum_{j=0}^{m}\sum_{k=0}^{i}C_i^k j^k \\ &=\sum_{k=0}^{i}C_i^k\sum_{j=0}^{m}j^k \\ &=\sum_{k=0}^{i}C_i^kf_k\\ &=\sum_{k=0}^{i-2}C_i^kf_k+C_i^{i-1}f_{i-1}+C_i^if_i\\ &=\sum_{k=0}^{i-2}C_i^kf_k+if_{i-1}+f_i\\ \therefore &if_{i-1}= (m+1)^i-0^i-\sum_{k=0}^{i-2}C_i^kf_k \end{aligned}$

这样我们就得到了递推式

错排

对于每个$n$，求出有多少长度为$n$的排列，使得$p_i!=i$。

我们设某个位置使得$p_j=n$，那么就分情况讨论：

1. 假设$p_n=j$，所以现在有两对错排已经确定了，那就是从剩下的$n-2$个数中选错排，而$j$的位置有$n-1$种可能，也就是$f_{n-2}\times(n-1)$。
2. 假设$p_n!=j$，我们把$p_n$移到$p_j$的位置，也就是说有$p_j!=p_j$，所以有一对错排已经确定了，还剩$n-1$对，那么就是$f_{n-1}\times(n-1)$

于是$f_n=f_{n-2}\times(n-1)+f_{n-1}\times(n-1)$。

解方程

计算$\sum_{i=1}^{n}x_i=m,x_i\ge{1}$的解的个数。

隔板法

把一个1看作一个小球

间隙插隔板

分组

组合数

$C(m-1,n-1)$

实际意义

选代表元

设$l_i,r_i$

每一对$l_i,r_i$对应着一个代表元，即方案

$x_i=l_i+r_i+1$

$\sum{x_i}=m$

设$l,r$都为$y$

$\sum(l_i+r_i)=m-n$

那就是$\sum^{2n}_{i=1}y_i=m-n$

y都加一

$\sum^{2n}_{i=1}(y_i+1)=m-n+2n$

设$y_i+1=z_i$

$\sum_{i=1}^{2n}z_i=m+n$

$C(m+n-1,2n-1)$

翻折法

遇到函数图像就把剩下的路径翻折

这样既可以求解不合法的方案数了

$C(n-k,m+k)$

Day7

1.

根据相对关系分三种情况讨论倒推出之前的位置。

2.

每段的下一个与当前字符的关系都是相同的，

其实就是字符匹配，KMP

3.

质因数分解

对于每个质数的指数相加起来，判断每个指数是不是k的倍数就可以了。

那么可以

维护每一位模k等于多少。

把每个区间维护成前缀和的形式，

那么区间求商那就是指数相减模k等于0

所以就是两个前缀模k意义下是相等的

维护一下模意义下的哈希就可以了

每一位都是0~k-1

递推的时候加一个数就进行哈希处理。

那么怎么对一个数快速进行质因数分解，

先用线性筛预处理出每个数的最小质因子，然后对每个数分别除一下就可以了。

哈希值要开大一些

4.

Alice n/2上取整

Bob n/2下取整

$\sum{v_i}+\sum{lcp(i,j)}$

可以dfs记忆化搜索一下。

对每个串进行赋值，那么就可以直接进行点权相减

$v_i+\frac{1}{2}\sum_j{lcp(s_i,s_j)}$

这样能保证两个点加起来正好lcp被加了一遍

这样sort一下然后计算即可

KMP

字符串严格匹配

前半部分和后半部分

假如已经知道了一个长串的border，那么加上一个字符，那就继续比较下一个字符

这么说同时去掉最后一个字符也是相同的。

对于一个更长的串，那么它的border是被比它短的border更新而来的。

也就是用短串的border推到长串的border

设nxt_i表示长度为i的前缀border长度

一个串可以有很多border，排序后小的border是大的border的border

那么就维护每一个border的状态

从下往上枚举看看哪个border的下一个字符是匹配的

字符串匹配

判断m在n中出现了几次

一个是hash，一个是kmp

P3193

dp_i,j表示考虑完前i个字符目前匹配长度为j，匹配可以用KMP

只要保证j<t就可以保证

然后把递推转化为矩阵快速幂就可以了

hash

比较两个东西一不一样。

类似于编码的过程。

$\sum{s_i\times{b^i}}$

对于字母串，每个字符串当成一个26进制的数，b=26

这么大的数肯定是存不下的，那就找一个大数取模

有$\frac{1}{p}$的概率相等。

优点：

判断t在s的某个位置是否出现

如何快速得到字串的哈希值？

前缀和预处理

也就是区间求和

$hash_i=hash_{i-1}\times{b}+s_i$

$\sum_{i=1}^n{s_i\times{b^{n-i}}}$

P2312

让左边右边同时模上一个大质数，然后我们求一下在模意义下是否等于0就可以了。

可以设多个模数，增加正解的概率。

P5537

对于走到每个节点，路径会产生一个序列，这个序列是唯一的，

每一个点都对应一个操作序列，

并且这个序列都唯一确定这个节点。

对于操作序列，若完全相等，那么到达的点相等。

每次对于这个$[l,r]$操作序列进行一个二分。

这个具有单调性，因为假如到这个操作序列的某个前缀已经走不通了，那么后面的也一定走不通。

所以我们要找的能走通的序列长度最长值。

对于每个点都处理出它对应的操作序列。

根节点是x？

也就是先到x再到要到的点，再进行拼接。

可以用线段树维护，可以合并两个哈希值

$h_1+h_2+\sum{B^{S_1}}$

Manacher

中间点很重要

一个回文串两边同时操作可以改变长度

来二分一下这个最长长度

回文中心

回文半径

abcba

!#a#b#c#b#a

感叹号是边界

b#b

这样回文中心就很显然了。

核心思想：求每个点的回文半径

回文半径即对应回文子串的长度

假设之前有串覆盖到了我这个点，那么就可以对称过去，最大为覆盖区间的右端点，最大继承到右端点，也就是继承对称点回文半径的信息。

对于这张图，红色点的回文半径已经求出来了，也就是对应红色的区间，下面我往后枚举，发现要求黑色点的回文半径的时候，这个点在红色点的回文半径内，这就意味着红色区间内有点与其对称，而对称的灰色点在之前已经被处理过了。

所以我们就可以继承灰色点的回文半径，也就是说我们不用再枚举一遍了，少走几十年弯路。

假如灰色点的回文半径并没有超过红色点，那么黑色点的继承到的回文半径也不会超过红色区间。

假如灰色点的回文半径超过了红色点，那么黑色点的继承到的回文半径只能到红色点的回文半径的边界，因为再往外黑色点和灰色点就不是对称的了。

因此总结下来就是继承到的回文半径的位置要和红色点回文半径的位置取个$\min$。

HDU5371

给定一个长度为n的数列 ，现在要求你找出最长的形似$s+s^R+s$的子串，$s^R$是$s$的反串。

两个回文中心。

只要两个回文半径可以互相覆盖到彼此的回文中心，那么就可以满足条件。

使满足这个条件下使两个回文中心间距最大就可以了。

$S_2-r_2\le{S_1}$

P6216

$t$在$s$中哪些位置出现了可以用 KMP 。

对每个位置处理出$s_2$是否可以从这里开始到完全匹配，

也就是对于每一个$s_2$匹配的位置，我在它匹配的左端点的位置加一。

查询时右端点要减去$s_2$的长度，这样就可以保证区间内的“1”都是合法的，这样就可以去找区间里1的个数来计算$s_2$出现的次数，

然后枚举这个点的回文中心，

所有回文子串的公差为$1$，

右端点同时减去$s_2$的长度后公差依然是1.

左右端点都是等差数列。

可以用前缀和优化：

然后我们其实就是要求剩下的这个三角形中所有点的和。

$\sum_{i=l}^{r-|s_2|+1}a_i\times(r-|s_2|-i+1)$

P5446

$R\le{S}$时，满足条件的$R$一定是$S$的前缀，所以我们枚举$S$ 的前缀，

若对于每个枚举的$R$，对它进行不断翻转，若得到的$R$不是$S$的前缀，那就跳过。

对于最后一步，是关于$R$右端点为中心的回文串，判断一下即可 ，如果可以就可以判断这个 R 串是否可以。

Trie树

树形结构，

从根走到底那就是一个字符串，

可以插入字符串，

没有出边就新建一条，

所以就可以用一棵树表示这个集合，

即一个字典树，

可以求 lcp，

即两个点 lca 的深度。

对于这颗Trie树上的字符串$\text{aba}$和$\text{abc}$，它们的lca是$b$，$b$的深度是$2$，因此它们的的$lcp$长度就是2。

01Trie

各种操作一样，字符集变成了0和1。

可以进行二进制操作

这样就可以对某个数得到异或值最大。

因为假如一个树二进制表示为$10110$，那么我就可以贪心地选择每位，如果可以我地最优选择是$01001$，假如某一位上没有我想要的（序列中没有该数），那就别无选择，但这样一个流程下来我得到的是最优解。

进行一个贪心

P3065

建一棵树，

把小于号换做有向边，

跑拓扑排序，

出现环了这条路就走不通，假如之前已经有$a<b<c$，

后面又从$c\to{a}$，说明$c<a$，那么就产生了矛盾，那么这条路就不能继续往下走。

CF178F3

树形背包问题。

$nS_ik$

$dep_x\times{a}\times{b}$

$nk$

$n$个节点转移，其它的节点复制，因为只有一个儿子

P4551

把一条路径拆成两段，

那就是$s$到根的异或和异或上$t$到根的异或和，

这个到根的异或和可以 dfs 处理一遍，

要找到一个$d_y$异或上$d_x$最大

对一个数求异或和最大，请问另一个数？

那就可以建01trie了。

可持久化

求$l,r$建出trie树

版本思想，

我有$q$次修改，那就有$q$个版本的 trie 树，

插入字符串的时候，新建一个部分 trie 树，这个trie 树上只保留信息改变的节点，也就是新加的节点和被影响到的原来的节点，

每个版本的trie树只需要记录根节点的信息。

对于没受到新节点影响的节点，直接对它们连接即可，

原来的查询可以照常进行。

P5283

枚举右端点，找到使得异或和最大的左端点。

对于$S_i$找到一个$max_{j<i}S_i{\oplus}S_j$

边查边插入右端点，用可持久化线段树。

最大值被选后，次大值才有可能成为答案，类似于超级钢琴

维护l,r，按照v用优先队列排序

大区间就会变成两个小区间，区间内的异或最大值可以用01trie解决

Exkmp

维护最右端点使得之前的lcp延伸到这个端点。

黑色为原序列，我现在要求每一个后缀与原序列的 lcp，即最大公共前缀。

比如我现在要求粉色点的 lcp，

但是发现这个点在当前最大lcp的右端点的范围内（红色线），即我们知道了灰色与黑色的 lcp，而灰色与蓝色的粉色部分又相同，于是蓝色和黑色的粉色部分也相同。

而对于粉色部分，我们已经知道了绿色与的 lcp，绿色<粉色，相同位置的绿色=粉色，于是绿色的 lcp 就可以被粉色点继承；假如绿色>粉色，但是超出部分在蓝色部分中不一定相同，因此最多能继承到粉色的边界处，因此绿色的 lcp的右端点下标要与粉色右端点下标取$\min$后继承。

而对于字符串$b$与字符串$a$的每个后缀的 lcp ，就可以把$a$接到$b$的后面，然后从长度为$a$的后缀开始扫就可以了。

每次维护的就是当前 lcp 延展到的最大右端点以及当前的递推数组，也就是用到的绿色的 lcp 的长度。

后缀长度由长枚举到短，第一次没有可以继承的，那就只能自己扫一遍了。

P7114

$n-border=len$

C即为$S-(AB)^i$

C是确定的，C中奇数的个数很好求，

然后枚举一个AB的长度，也就是循环节的长度，再枚举一个循环的次数，

若$len|n$，那么$len$即循环节，用这个判断我们枚举的AB长度是否合法。

AB会在这个循环节内出现，A出现的频率为$1\sim{len-1}$，所以就枚举所有的A，

然后用桶记录每个奇数出现的次数，加起来，看看是否满足$F(A)<F(C)$，那就累加答案。

Day8

1.

树形 DP

设$f_x$代表从$x$出发到其子树内最长链的长度。

转移就是$f_x=\max(f_x,f_y+(a_x\oplus{a_y}))$

$ans=\max(ans,f_x+f_y+(a_x\oplus{a_y}))$

2.

用$f_{x,y}$代表从$y$出发到$x$的路径条数。

可以拓扑排序并转移。

若$z$是$x$的一个前驱，那么$f_{x,y}+=f_{z,y}$

由于我们只关心奇偶性，因此只记录0 1就可以了，转移就是$f_{x,y}=f_{x,y}\oplus{f_{z,y}}$。

用bitset维护就可以了。

3.

$dp_x$表示让$x$值为1的最少子树中$1$的个数。

看下$dp_1$是否大于1的个数。

4.

前i个数已经分成了j个集合的方案数，转移：

$S_{n,m}=S_{n-1,m}\times{m}+S_{n-1,m-1}$

树上？

按照bfs序 DP

$S_{3,k}$

$S_{4,k}=S_{3,k}\times{k-2}+S_{3,k-1}$

$S_{n,m}=S_{n-1,m}\times{m-dep}+S_{n,m-1}$

要么就加到剩下的集合，要么就自己新开一个集合。

从上到下 DP。

这样就能保证DP到一个点的时候，它的祖先已经处理好了。

P3304

求有多少条边满足所有直径都经过该边。

• 直径是一定有交点。
• 如果分叉了，那么两端是一样长的，否则就可以有更大的直径。
• 两个树，两个直径，将两棵树的根节点连接起来，一共可能有六条直径。

从树上某个点dfs，深度最深的点一定是某个直径的端点，

查路径长度直接查LCA就可以了。

先找出来一条直径，

从右端点 DFS，

对每个点记录它到子树里最深的一条链，

然后如果和当前点到右端点的长度相同，那么就可以替代，

执行完所有的操作后主链上剩下的就是公共的边。

P3177

一条边被多少个点对经过就是它的贡献。

其实就是这条边左右两边黑色点的对数加上白色点的对数。

设$f_{x,t}$表示在x子树内选了t个黑点，最小贡献是。

新加子树y，

$f_{x,a+b}+=f_{x,a}+f_{y,b}+v(x,y)$

$a(k-a)+(S-a)\times{(n-S)-(k-a)}$

合并的时候$a:0\sim{S}$

n方个点对，那就是n方

P3174

$f_x$表示从x开始向子树里找一条链使这个毛毛虫最大。

枚举儿子

$f_x=f_y+sum_x+1-1$

在lca处合并

找最大的两个$f_y$

$f_x=f_{y_1}+f_{y_2}+sum_x-1(+1)$父节点

CF1153D

$dp_x$表示x为1儿子最小填1的个数，

对于max和min分别讨论

---

设$dp_x$设x在子树中有s个叶子，x最多能排多少名。

1:

$f_x=\max(s-\min(s_i-f_i))$

0:

$f_x=\sum{(f_i-1)}+1$

P3523

对K二分，

也就是以每个我选的点为中心，K为半径形成一片覆盖区，如果能全部覆盖全部关键点，那这个K就可以满足。

如上图，红色点为关键点，蓝色点为我选的节点，蓝色⚪为当前覆盖区，显然，上图为一种合法的方案。

对于每一个点和一个K，一定是让一个关键点再覆盖范围边界被覆盖到是最优的，因此我们要让这些关键点刚好卡上这些边界，这样就可以使它可以覆盖到更远的点。

所以我们定义$f_x$代表x子树中最远还没有覆盖的点的位置，如果这个距离等于K了，我就在这里选一个点。

定义$g_x$代表覆盖到的最近的已经选的点。

如果某个关键点到$y$的距离即$f_x+g_x\le{K}$，那么这个关键点就会被波及。

那么就可以更新$f_x=-INF,g_x=0$

1453

基环树

树上问题是求解最大独立集

设$f_{x,0/1}$x这个点选/不选，子树的最大权值

选了那就是x的权值加上儿子都不能选

对每个子树做一个DP，每个点对应选这个点对应的权值和不选这个点对应的权值。

P4381

设$f_x$表示从$x$到其子树的最长路径是多少。

断环为链，记录链上的路径前缀和$S$，答案就是

枚举 $y$并维护$x$的前缀最大值

CF187E

选了根节点之后，答案就是每个点的子树大小之和。

换根DP

$f_y=f_x+n-2\times{size_y}$

把x换到儿子y上。

P2986

换根DP

$f_y=f_x+size_x\times{w}-size_y\times{w}$

P4438

对每个点记录x y有多少，

$f_{x,j,k}$x节点，j个l，k个r的贡献大小。

P2014

在x的子树中选了大小为i的子树得到的最大价值

$dp_{x,i+j}=dp_{x,i}+dp_{y,j}$

$dp_{x,1}=a_x$

$O(n^2)$

只要下标小于等于$size$，那么就是两两配对$n^2$的

LOJ160

dfs 序——后dfs优化背包

先 dfs 子树，再把根计入。

只有递归完了子树，根节点才会被假如

$dp_{x,i}$　dfs序到了x在这里，总递归完的子树为i的方案

$dp_{x,i}=\max(dp_{x-size_x,i},dp_{x-1,i-w_i}+v_i)$

P1080

$a_i,b_i$

交换：微扰法

把所有的人的$a_ib_i$排序

P3574

设$f_x$为只走x子树中的点，所求的最小值。

$dp_i+2\sum_{i<j}size+1$

类似于国王的游戏

$b_j+a_i\le{b_i+a_j}$

$a_i-b_i$越小越放到前面。

Day9

NONE

Day10

1.

2.

设$dp_{i,j}$为从某个1开始走到i,j的最小花费。

而每一层点特别多的时候就可以用多源最短路。

$f_{i,j}=\min({f_{i_1,j_1}}+|i-i_1|+|j-j_1|)$

令$f^1_{i,j}=\min({f^1{i_1,j_1}})+i+j$

然后就可以将第一维排序，

然后查询的时候就相当于查询第二维的区间最小值，这样就可以用线段树或者树状数组来做。

插入点的优先级要比查询的优先级高。

就可以分成两个象限来处理，$x<0/x>0$。

3.

暴力枚举点对可以$n^2$解决。

可以先把一个点和它所有互质的点都预处理出来。

对每个点维护一下到根有多少互质的点。

然后就可以用树上差分，$O(n^2)$预处理,$O(1)$查询。

我们只关心质因子的种类，而不是个数。

那么其实就是两个集合的交集为空。

容斥？

$(^{r-l+1}_2)-\sum_P(^{cut_p}_2)+\sum_{PQ}(^{cut_{PQ}}_2)-\sum_{PQR}(^{cut_{PQR}}_2)$

加入元素？

删去元素？

莫队

一个序列，长度为n，每次区间询问。

先把这些询问按照某种方式打乱顺序。

pair

KD-Tree

Unordered Map

Day11

1.

按照a排序

维护前缀和

枚举r的同时更新与l有关的变量的最小值

2.

令f为长度为i有j个顶的个数

每次插入新排列的最大值，

插入再原本的顶旁边顶的数不会变，

最左边和最右边也不会变，其它地方顶的数量就会加一。

3.

将点按$x_i$排序。

$dp_{i,0/1}$表示第以i个点为端点向左/向右的方案数。

4.

假如$a_i<a_j$，在满足$i<k<j$的情况下，$a_k>a_i$，这个时候以$k,j$作为前两位更优，因为大小和第三个数的选择范围；

假如$a_i>a_j$，中间存在一个$k$满足$a_k>a_j$，这个时候$i,k$更优。

所以这个时候对一个点，选左边/右边的第一个比它大的数更优。

有用的前两个数只有$O(n)$个。

对询问按照左端点从大到小排序。

对序列从右向左扫描，每次找一个c的最大后缀，也就是找到$a_i+a_j$的最大值，来和我当前的这个点$k$匹配，而$k>=$某个数，所以是最大后缀，用线段树维护。

P8819

给每个点随机一个权值，

统计所有起点的点权和和所有点的点权和。

如果相等，那么说明符合。

那么就维护每个点以它为终点的激活边的起点的权值和与每个点以它为终点的失活边的起点的权值和，然后每次进行这种操作的时候给对应加上或者减去对应权值和即可。

Day12

1.

海底高铁

2.

同Day7 T1

3.

每个点记录以它为左上角/右下角为顶点的正方形的最大边长，

那么边长区间就是$l\sim{l_{i,j}}$ 。

如果组成正方形，那么两点处于对角线位置，再判断左上角的长度是否合法和右下角长度是否合法。

三个条件：

$l_{x_1,y_1}\ge{x_2-x_1}$

$r_{x_2,y_2}\ge{x_2-x_1}$

$x_2-x_1\ge{l}$

所以就枚举对角线，算对角线上的两个点

枚举$x_2$，看有几个合法的$x_1$

那就分别算$1\sim{l-1}$和$1\sim{r}$所有$\ge{x_2-l_{x_1,y_1}}$的点，$O(1)$查询。

可以树状数组

4.

又是全排列

$dp_{i,j}$代表考虑了前i个数，选择情况为j（二进制下表示，0代表未选，1待选已选），这种情况下的逆序对数。

状压 DP