Ideas and Tricks

阅读原文时间：2023年07月11日阅读：3

1.树上拓扑排序计数

结论$\dfrac{n!}{\prod\limits_{i=1}^n size_i}$

对于节点$i$，其子树随意排序的结果是$size[i]!$

但$i$需要排在第一位，只有$size[i]-1$个数可以任意排

乘上$\frac{1}{size[i]}$

2.DAG上的问题退化成有向树解决

如果转化为DAG问题的题目，如果边与边之间有传递关系

可以退化成树进行解决

在建树的时候需要关心的是某一个点的直接父亲是什么

如ATcoder的ABC158F

3.在基环树上DP

主要思想是将基环树上的环断开，然后做树形DP

最后处理这一条边对答案的影响

4.在数列上划分并要求划分区域递增的DP

基本的DP转移是

$dp[i][j]=max{dp[j][k]}+v(i)$

其中 $i$到$j$的区间和大于 $j$到$k$的区间和

朴素复杂度$O(n^3)$

可以使用单调队列优化到$O(n^2)$

利用固定j的取值

所以$i$增加的同时，$k$的范围也相应变大，利用单调队列和单指针维护

例如P3089

但如果$v(i)$有单调性，可优化到$O(n)$，如P5665

5.求$depth[LCA(i,j)]$处理办法

将$i$到$root$的路径所有的点权值加一，然后询问$j$到$root$的路径的点权之和，就是$LCA$的深度

$LCA$可以看成两个点到根的两条链的第一个交点

6.LCT维护边权

将边看作一个点，将这个代表边的点的点权赋为这条边的边权，并将其他的点边权设为$0$或其他不影响答案的值

在连边或断边时，设这条边两端的端点为$u$,$v$，代表边的点编号为$id$

link(u,id),link(id,v);
cut(u,id),cut(id,v);

7.LCT维护子树信息

维护一个点由虚边连结的点的信息$si$，然后再维护所有的边（包括虚边和$Splay$上左右儿子）相连的儿子和自己的信息$s$

因为虚实边会随着LCT的操作不断变化

首先在$pushup$的时候，$s[x]=s[son[x][0]]+s[son[x][1]]+si[x]+val[x]$，保证$s$的值实时更新

$access$的时候因为去掉了$x$之前的实儿子（变为了虚儿子），增加了一个新的实儿子（由原来虚儿子变来），$si$一加一减，$s$不变化

for (int y=0;x;x=fa[x])
{
splay(x);
si[x]+=s[son[x][1]];
son[x][1]=y;
si[x]-=s[son[x][1]];
pushup(x);
y=x;
}//access

在$link$的时候增加了一条虚边，改变$y$的$si$，要注意要将$y$转到根上，以免改变其他节点的值

inline void link(int x,int y)
{
makeroot(x);
access(y);
splay(y);
fa[x]=y;
si[y]+=s[x];
pushup(y);
}

$cut$因为切掉的是实边，对$si$无影响，注意$pushup$即可

还有这里可以维护的信息是满足加减性的，如子树大小，子树权值和

但像子树权值最大值是不满足加减性的，不能维护（据说可以每个节点将$si$和$s$改成一棵平衡树）

在求出$x$子树的信息的时候，$access(x)$后取出$si[x]$即可

8.维护区间中位数

可以二分答案，将$>=x$的数标记为$1$，$=$当前二分的数，若某一个区间的和小于$0$，则这个区间的中位数$<=$当前二分的数

9.对于题目条件限制的转化

对于一些要求最大最小值的题目，然后题目对选择（操作）集合有限制的，比如取$min$,$max$操作，那么可以试图构造出一个原集合的一个超集（相当于将题目条件变弱），使得超集中的每一个元素都存在原集合中的元素比它更优或相同。简单来说就是放宽题目条件，使问题更加好处理，虽然可能将题目条件放宽之后，有一部分元素不合法，但这些元素都能在原集合中找到比它更好的元素出来，所以这些元素不会变成答案

例如AGC28C

10.树上任意一点的最远距离

树上任意一点的最远距离就是树上直径的两个端点到该点距离的较大值

证明：利用反证法

对于一条直径两个端点$u$,$v$

若存在一条路径$x->y$，且满足$len(x,y)>len(x,u)$,$len(x,y)>len(x,v)$

设直径和路径的交点为$a$

则可以找到一条比原来直径更长的路径$u->a->y$

与直径的定义矛盾

11.树联通块直径合并

两个树联通块合并之后，直径的两端点一定在原来两个联通块的直径的四个端点内

然后在这四个端点处枚举即可，判断剩余两个点是否在选出的两个点形成的路径上

$P.S.$ 判断一个点在一条路径上的充分必要条件是

设路径为$x->y$，当前要判断的点为$u$

那么$depth[u]>=depth[LCA(x,y)]$并且 $LCA(u,x)=u$或$LCA(u,y)=u$

12.$\sigma$因数函数

性质：

$$\sigma _{0}(i*j)=\sum_{x\mid i}\sum_{y\mid j}[gcd(i,j)=1]$$

多维情况

$$\sigma_k (AB) = \sum_{x|A} \sum_{y|B} [\gcd(x,y)=1] (x \frac{B}{y})^k = \sum_{x|A} \sum_{y|B} [\gcd(x,\frac{B}{y})=1] (x y)^k$$

三个因数相乘情况

$$\sigma_k (ABC) = \sum_{x|A} \sum_{y|B} \sum_{z|C} [\gcd(x,\frac{B}{y})=1] [\gcd(y,\frac{C}{z})=1] [\gcd(x, \frac{C}{z}=1)] (x y z)^k$$

证明待填……

不填了……

13.循环矩阵

形如上面的矩阵称为循环矩阵，可以通过只记录第一行来保存矩阵的所有信息

$m_{x}=\sum_{(i+j-2)\%n+1=x} m_{i}m_{j}$

那么可以$O(n^{2})$的时间内计算

将下标减1

$m_{x}=\sum_{(i+j)\%n=x} m_{i}m_{j}$

NTT计算即可

做到$O(nlogn)$

14.期望DP的转移

由于期望DP常常是由结束状态推到状态，并且不确定性，常常会出现既要从前面转移当前DP，又要从后面转移当前DP，会导致需要高斯消元，但不过高斯消元的常规复杂度都是$O(n^3)$，复杂度较大，并且难以优化。但如果DP转移方程，项数较少，可以利用数列的递推，来进行解决

以[六省联考2017]分手是祝愿为例

DP转移方程：$dp[i]=\frac{i}{n}dp[i-1]+\frac{n-i}{n}dp[i+1]+1$

可以发现这个式子可以直接高斯消元，但时间复杂度承受不起

考虑可以设一个递推关系，可以注意到dp[i]只跟前后两项有关

那么设$dp[i]=dp[i-1]+f[i]$

代入$dp[i]=\frac{i}{n}(dp[i]-f[i])+\frac{n-i}{n}(dp[i]+f[i+1])+1$

化简得到$f[i]=\frac{n-i}{i}f[i+1]+\frac{n}{i}$

那么就可以从后往前递推得到$f$

可以根据具体题目的转移方程来改变设的数列

15.多项式DP，拉格朗日插值

DP如果某一维定义域很大，如果初始边界值是多项式的话，可以考虑这个DP是一个多项式，可以拉格朗日插值求出某一项我们需要的值

如果证明的话，可以通过归纳证明，先设上一个是多项式，代入递推式，将相同次数的项提出来，观察即可

常用自然数次幂的公式，记$g_i(x)=\sum_{j=1}^{x} j^i$

$(i+1)g_{i}(x)=(x+1)^{i+1}-1-\sum_{j=0}^{i+1}C_{i+1}^{j}g_{j}(x)$

可以递推，可以拉格朗日插值求特定值

16.二项式反演

$f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i$

常用形式 $f_n = \sum_{i=0}^n {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i$

注意这里下标可以不从0开始，也可以倒序枚举

容斥的时候可以使用二项式反演

至多和恰好的转换，设$g[i]$为至多$i$个的方案数，$f[i]$为恰好$i$个的方案数

$g[i]=\sum_{j=0}^{i}C_{i}^{j} f[j]$

二项式反演得到 $f[i]=\sum_{j=0}^{i} (-1)^{i-j}C_{i}^{j}g[j]$

至少和恰好的转换，设$g[i]$为至少$i$个的方案数，$f[i]$为恰好$i$个的方案数

$g[i]=\sum_{j=i}^{n}C_{j}^{i} f[j]$

二项式反演得到 $f[i]=\sum_{j=i}^{n} (-1)^{j-i}C_{j}^{i}g[j]$

但这样可能难以找到什么实际意义来解释

考虑至多和恰好的转换，对于一个需要求出恰好$k$的方案数，先找出问题至多的下界记作$least$，那么当有$least$个的时候，至多和恰好的方案数相同，那么向前递推。在递推过程中，每一项都可以计算出至多的方案数，先乘上$C_{k}^{i}$，减去之前计算好的前缀和，表示减掉比$i$小恰好的方案数，直到递推到$k$

至少同理

17.上升幂下降幂和斯特林数

$x^{\overline{n}}=\sum_{k=0}^{n}\begin{bmatrix}n\\k\end{bmatrix} x^{k}$

$x^n=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}$

第一类斯特林数递推式

意义：$n$个不同元素形成$m$个圆排列的方案数

$\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}$

第二类斯特林数递推式

意义：$n$个不同元素放入$m$个相同的盒子，盒子不可空

$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n\\k\end{Bmatrix}$

有通项公式

$s(n,m)=\frac{1}{m!}\sum_{k=0}^{m} (-1)^{k}C_{m}^{k}(m-k)^{n}$

可以卷积

18.完全图

建反图，那么原来的完全图，在反图上就是一堆独立的点，互相没有边连接，判断即可

19.矩阵乘法

如果矩阵乘法在中间有断点的话（也就是需要分成若干段，每一段分别做矩阵快速幂），可以先预处理出来转移矩阵的2次幂的次数，那么通过二进制拆分就可以得到任意转移矩阵的次幂，在转移的分段的时候不需要每次乘一个$n*n$的大矩阵，可以乘一个一行的向量，向量和矩阵的乘法是$O(n^2)$，那么每一段的时间复杂度就是$O(n^2logMAX)$，预处理复杂度$O(n^3logMAX)$，那么总复杂度就是$O(n^3logMAX+kn^2logMAX)$

20.利用树剖维护修改所有儿子信息

可以先修改节点和重儿子的信息，并将修改的信息记录在节点上，在询问的时候跳轻边的时候，将信息更新即可

21.区间DP的模型

对于操作为删除一段连续的区间，然后将左右两端的区间拼接起来的操作，可以考虑以下的$dp$状态设计

$dp[l][r][k]$表示删除$[l,r]$这个区间并且$[l,r]$这个区间左边与$a[l]$信息有关的位置个数有$k$个的代价

转移时$dp[l][r][k]=dp[l+1][i-1][0]+dp[i][r][k+1]+…$，其中$a[i]$与$a[l]$相等

或者$dp[l][r][k]=dp[l+1][j][k+1]+…$

复杂度为$O(n^4)$，跑不满，$100$随便跑

考虑这样设状态的原因，因为删除一段区间可以将两端的信息拼接起来，如果直接记录左右两端的信息会需要两维的DP，那么在某一个拼接起来的区间的最右端记录左边的信息，那么可以用一维的空间记录下。在转移的时候，第一个的转移方程就是在中间扣掉一段区间，将之前左边的信息合并到当前来

有关的题目

[COCI 2010] ZUMA和Vasya and Binary String

$P.S.$上面两道题都有另外一种设DP的状态

设$dp[l][r][k][kind]$表示$[l,r]$这个区间中最终删完之后剩下了$k$个种类为$kind$的元素的代价

$f[l][r]$表示$[l,r]$这个区间完全删完的代价

明显，可以用$dp[l][r][k][kind]$直接更新$f[l][r]$

$dp[l][r][k][kind]=f[l][i-1]+dp[i+1][r][k-1][kind](a[i]=kind)$

要有一个前提就是一定删除一个长度为$x$的区间$f(x)$优于$f(a)+f(b)$,$a+b=x$

所以剩下的一定是一个前缀（后缀，两个都可以）

22.扩展欧拉定理（欧拉降幂）

$a^{x}\equiv \left\{\begin{matrix}a^{x \mod \varphi (p)} & gcd(a,p)=1 \\ a^{x} & gcd(a,p)\neq 1,x<\varphi(p) & \\ a^{(x \mod \varphi(p))+\varphi(p)} & gcd(a,p)\neq 1,x\geq \varphi(p)\end{matrix}\right.(\mod p)$

Power Tower

23.关于某一状态转移到另一个状态可行性问题

一句话：可以考虑在操作中不变的量；或者找到一个中继状态，使得两个状态都能达到这个状态

24.线性基

离线下来，在线性基里面优先存储较晚删除的数，在判断一个数是否是在线性基里面，只要尝试插入线性基，如果这个数不能成功插入线性基，并且用到的线性基中的元素的删除时间都在当前时间之后，那么这个数就可以被异或得到

struct liner
{
int d[40],t[40];
inline void insert(int x,int id)
{
for (int i=29;i>=0;i--)
{
if (!((x>>i)&1)) continue;
if (t[i]>i)&1) x^=d[i];
}
}
inline int query(int x,int l)
{
for (int i=29;i>=0;i--)
{
if (!((x>>i)&1)) continue;
if (t[i]<l) return 0;
x^=d[i];
}
return 1;
}
}T;

一些性质

线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
线性基是满足性质 1 的最小的集合。
线性基没有异或和为 0 的子集。
线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
线性基中每个元素的二进制最高位互不相同。

线性基的严谨定义

向量空间$V$的一组向量若满足

1）线性无关

2）$V$中任一向量可由此向量线性表出，则称该组向量$V$中的一个基（亦称基底）。

上面讨论的线性基中的向量可以看成一个数的二进制表示，向量中每一个元素都为$0$或$1$，并且定义向量的加减法为模2意义下进行的。其实构造线性基的过程中，就是在判断试图插入的向量是否跟之前所有的向量线性相关，如果线性相关那么就不插入到线性基中，如果线性无关那么就插入到线性基中

就是在解$a_1x_1+a_2x_2+…+a_nx_n=b$模$2$意义下的这个方程组（向量中每一个维都可以列出一个方程）

而解这个方程的基本思路就是，把当前的最高位先消元消掉，不断消下去，看能不能得到$0$，如果不行说明这个向量于之前的向量线性无关，插入线性基中

那么这种线性基的构造方式可以推广到$n$进制下的异或（不进位加法），思路跟二进制下的一样，先利用之前的向量试图把最高位给消掉，直到消不掉或者当前向量被消成了$0$

应用：扩展NIM博弈（先手必败条件：每一堆个数拆分为$2$进制下，每一位为$1$的个数$\%(d+1)=0$)

25.博弈论

所有$ICG$游戏，都可以转变到$DAG$图上游走游戏

一般要将状态归成一个简单的规律，然后可以试图证明这个规律

证明有三步：

1.证明最终状态是必败态

2.证明必胜态可以转移到一个必败态

3.证明必败态只能转移到必胜态

基本模型有：巴什博弈，NIM博弈（EX），威佐夫博弈（EX），斐波那契博弈

NIM博弈结论：每一堆石子异或和为$0$时，先手必败

EXNIM博弈结论：每一堆个数拆分为$2$进制下，每一位为$1$的个数$\%(d+1)=0$，先手必败

威佐夫博弈：第k个必败态为$\left (\left \lfloor \frac{1+\sqrt{5}}{2}k \right \rfloor,\left \lfloor \frac{3+\sqrt{5}}{2}k \right \rfloor \right )$

可以利用Betty定理证明（$\frac{1}{a}+\frac{1}{b}=1$，$Spec(a)$和$Spec(b)$分别为正整数的划分，并且没有交集）

$b=a+1$（第一项），带入即可

斐波那契博弈：当石子数为斐波那契数时先手必败

阶梯博弈：

两个绝顶聪明的人在玩游戏，有$n$堆石子，每次每人可以取走第$i$堆$(i>1)$任意数量的石子并将它们放到第$i−1$堆，或者直接取走第一堆的任意数量石子，不能操作的人输，请问先手能否必胜？

对于这一类问题我们将堆的编号分奇偶考虑，如果只有奇数编号那些堆石子，这就是一个尼姆博弈。现在加入了偶数编号的堆，同样不影响答案，因为如果有人将偶数编号第$i$堆的石子移到第$i−1$堆，那么另一个人可以将上一个人操作的那些石子从第$i−1$堆再移到第$i−2$堆，这样奇数编号堆的局势没变，两人的先后手关系也没变，相当于将偶数堆编号的石子往前移了两次。而移动奇数堆到偶数堆就相当于拿走了石子。

SG定理：由$n$个$ICG$游戏组合起来的游戏，先手必败的条件为$SG(a_1)\ Xor\ SG(a_2)\ Xor\ …\ Xor \ SG(a_n)=0$

26.平面图欧拉定理

$$V+F=E+2 \tag{25.1}$$

其中这个公式在连通图的情况下成立，其中$V$为图的顶点数，$E$为图的边数，$F$为这张图把平面分成了几个部分（包括图以外的一个平面）

$$V+F-E=K+1 \tag{25.2}$$

$V$,$F$,$E$跟上文表述一致，$K$表示整个图形中有$K$个联通图，其中$K=1$时即为$(25.1)$

应用：网格图上求连通块

题目:「APIO2017」斑斓之地

27.多项式全家桶

首先要知道两个东西，牛顿迭代和泰勒展开

先讲泰勒展开

$f(x)=f(0)+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\dots \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)$

一种形象的理解方式是：对于一个光滑的曲线考虑用一个多项式函数去逼近它，首先考虑的是先选取原来函数上一个点，是多项式函数经过这个点，这仅仅是保证在这一个点上多项式函数和原函数相同，那么考虑如何更精准的逼近，函数的性质中最先注意到的是函数增减性，也就是函数的导数，那么让多项式函数在这一点的导数也和原函数的导数相同，保证这一点之后，会发现多项式函数和原来的函数趋势已经相同，之后就考虑函数凹凸性，即二阶导数，之后以此类推，不断逼近，就得到上面的表达式

29.最大化AND,OR

当操作是XOR时可以简单地利用Trie来进行维护，但当是AND的时候，由于当去匹配的数当前这一位是0时，不知道应该是走0还是1，如果两个子树都走下去的话，复杂度不对，那么考虑将1子树合并到0子树上，然后查询的时候如果当前这一位是1那么走1子树，如果是0就走向0/1子树。这样单次询问就是$O(m)$，预处理为$O(m2^m)$，$m$为位数，适用于$m$比较小的情况

30.点分树

点分树就是在点分治的时候将每一层的重心连起来所形成的一颗树，具有一些优良的性质

1.首先点分树的最大深度为$log_{2}^n$，可以通过这个性质来在点分树上维护一些点分治可以维护的信息，记录点分树中子树的信息，通过修改询问的时候不断跳父亲，来得到答案，但同时这里需要注意，在从$x$跳到$fa[x]$时，如果直接统计$fa[x]$的所有子树信息，会把x子树重复统计，那么就需要在每一个节点记录这个子树到节点父亲的信息，最终容斥计算

这里的空间复杂度$O(n*pertime)$，时间复杂度$O(nlog_{2}^{n}*pertime)$

2.点分树还有具有类似Kruskal重构树的性质，对于节点$x$，任意两个节点$u,v$，保证$u,v$不在$x$在点分树的同一棵子树，那么$u->v$一定经过$x$，那么$dis(u,v)=dis(u,x)+dis(x,v)$，那么可以利用这个性质来加速一些在树上跳的问题