notes

c++ 将函数名作为函数参数的具体操作

1.直接使用

int f(int a){rturn a+1;}
int use_f(int a,int (*func)(int)){return f(a);}
int main()
{
    int a;
    cin>>a;
    cout<<use_f(a,f)<<endl;
}

2.在结构体中使用
由于在结构体中直接如上的使用报错“非静态对象不能这样使用”，所以需要加上static

struct test
{
    static int f(int a){rturn a+1;}
    int use_f(int a,int (*func)(int)){return f(a);}
};
test T;
int main()
{
    int a;
    cin>>a;
    cout<<T.use_f(a,T.f)<<endl;
}

对于“删除某元素后剩余元素的运算值”问题的快速解法

如果答案可以通过增量法快速求出，则可以：
用f[i][j]表示删除了i到j后剩余元素的运算值，通过f[i][j]求出f[i][mid]和f[mid+1][j]。总的时间复杂度为O(nlognf(n))，其中f(n)为新增加一个元素的时间复杂度。
这个方法可以用在：

• 去除一个元素的高斯消元
• 不经过一个点的最短路

模意义下的矩阵消元(上三角化)

如果模数是素数：使用费马小定理求逆元进行除法。
如果模数不是素数：辗转相减。

LIS类问题的树上求解

利用multiset

• 求父节点权值>子节点权值，全局最多选几个点

对序列求lis时，我们可以将数字依次放进multiset中，每次新加入一个数字，删除其lower_bound，插入其本身。
对树求lis时，启发式合并每个字树的multiset，删除父节点lower_bound,插入父节点。

竞赛图

• 设D为有3个以上顶点的强连通竞赛图，则对于每个$x\in V_D$和每个整数$k\in [3,n]$都有一个k元环通过x。
• 任何一个竞赛图都含有一条Hamilton路
• 任何一个竞赛图包含Hamilton环当且仅当其联通

仅给出定理1的证明思路：
运用数学归纳法，当(n-1)个点的竞赛图满足定理1时，我们证明n个点的竞赛图也满足定理1.
添加一个点后，此点必定与之前的点的连边既有入边也有出边。假设全部都是出边，现给定一个入边。这样一定使该图存在一个n简单元环。然后证明对于该点存在[3,n-1]元环。
反证法：对于经过该点的k元环，确定之前n-1个点的n-1元环，那么在环上每隔k-1个点都必须与该点连入边。如果$k-1\not| \ n-1$，则一定可以找到这样的环。如果$k-1|n-1$，则通过这些连入边的点之间的连边，也一定可以找到一个k元环。

对于竞赛图类的问题，一般在拓扑排序后对图进行分析。

例题，test20180926，求双色边的竞赛图是否满足，每一种颜色的子图中都满足若存在$(u,v),(v,w)$则一定存在$(u,w)$。该题利用到如下结论：该性质存在当且仅当在一个子图中联通的两点在另一个子图中不连通，且每个子图不存在环。因此，将两个图正反合并在一起，找是否存在环即可。直接传递闭包最快是$O(\frac{n^3}{\omega})$的，而这种方法可以做到$O(n^2)$

点分治

由于动态点分治中子树之根并不连续，所以必须利用LCA求原树上的树上距离。
RMQ求LCA时需要在遍历子节点的同时不停在dfs序列内插入当前节点以维持最小值的准确。这样只会带来2的常数。

LCT

lct最灵活之处在于可以动态维护一棵树的形态(利用区间翻转标记)。

void access(int a)
{
    int b=0;
    while(a)
    {
        spl(a);
        tre[a].s[1]=b;
        upd(a);
        b=a;
        a=tre[a].f;
    }
}
void sroot(int a)
{
    access(a);
    spl(a);
    tre[a].rv^=1;
}
void cut(int a,int b)
{
    sroot(a);
    access(b);
    spl(b);
    tre[b].s[0]=tre[a].f=0;
    upd(b);
}
void link(int a,int b)
{
    sroot(a);
    tre[a].f=b;
}
int qmax(int a,int b)
{
    sroot(a);
    access(b);
    spl(b);
    return tre[b].mxp;
}

尺取法

利用类似“毛毛虫”的一种解构维护一段连续的东西的方法。

• 如“最大连续字段和”,用左右两个端点维护中间的值最大。如果中间的值为负则收缩为0。

• 又如NOI2016"区间"，用左右两个端点维护当前可以产生m覆盖的所有区间。

这样，在平移这个“尺取”出的毛毛虫时，我们可以只是简单的处理左右端点的变化，这样可以依靠题目原本的单调性使总复杂度变成$O(n*F(n))$

分块枚举法：

对于一类需要多次进行“存储”与访问的操作，有时存储耗时多，而访问极其容易；或者访问耗时多，存储极其容易。

比如在一个数不超过$10^{18}$的集合里寻找x的倍数的个数，且已知所有数都是一个$10^{18}$以内数$Y$的约数，这时访问操作变成了$O(n)$或者$O(\frac{10^{18}}{x})$的了，而存储为$o(1)$，这时我们可以让存储让一步，使访问变快，最终两者速度达到平衡，利用均值不等式，我们知道两者复复杂度相近时总复杂度最低。

具体的做法是，将每个数分解质因数，将质因数划分为两个集合，使这两个集合可以组成的数的个数相近。对于一个$X=A*B$，我们将X的贡献加入到$\forall b|B \ , \ f[A][b]$中，查询时求$\forall A|a \ , \ f[a][B]$的和即可。如果$Y$的约数个数为$\sigma$，则存储和访问的时间复杂度都是$O(\sqrt{\sigma})$。

这样的问题，比如CTSC2017吉夫特，以及湖南省队集训2018陈江伦的一道题。

对合数取模的技巧

在一类问题中，如利用Burnside引理求本质不同的环染色方案数时

$$\begin{align} ans &= \frac{1}{n}\sum_{i=1}^{n} c^{gcd(i,n)} \\ &= \frac{1}{n}\sum_{d|n} c^{d}\phi(\frac{n}{d}) \end{align}$$
最终要将答案除以n，而只有在模素数意义下这个可以用逆元完成。所以我们可以在计算时对$pn$取模，最终将答案除以n即可。

同样，这个技巧可以利用于对合数取模的FWT中

一类数论问题的分析手段

1.约数个数函数

$$d(nm) = \sum _ {i|n} \sum _ {j|m} [gcd(i,j)=1] \\ $$

所以约数个数函数的二维前缀和可以这样化简：

$$\begin{align} \sum _ {n=1}^{N} \sum _ {m=1}^{N} d(nm) & = \sum _ {n=1}^{N} \sum _ {m=1}^{N} \sum _ {i|n} \sum _ {j|m} [gcd(i,j)=1] \\ & = \sum _ {i=1}^{N} \sum _ {j=1}^{N} \lfloor\frac{N}{i}\rfloor\lfloor\frac{N}{j}\rfloor [gcd(i,j)=1] \\ & = \sum _ {d=1} ^ {N} \mu(d) \sum _ {a=1} ^ {\lfloor\frac{N}{d}\rfloor} \sum _ {b=1} ^ {\lfloor\frac{N}{d}\rfloor}\lfloor\frac{N}{ad}\rfloor\lfloor\frac{N}{bd}\rfloor \end{align}$$
令$f(n)=\sum _ {i=1} ^ {n} \lfloor\frac{n}{i}\rfloor$
则
$$\sum _ {n=1}^{N} \sum _ {m=1}^{N} d(nm) = \sum_{d=1}^{N}\mu(d)f(\lfloor\frac{N}{d}\rfloor)^2$$
以上的玩意都可以$O(N^\frac{3}{4})$求解。如果预处理前$O(N^\frac{2}{3}/\log^{\frac{1}{3}}n)$个$\mu(d)$和$f(d)$，这东西就可以$O(N^\frac{2}{3}\log^{\frac{1}{3}}n)$求解了。

如果用线性筛预处理$f(d),\mu(d)$，可以做到$O(n^\frac{2}{3})$

如果$N\leq 10^7$有另外一种更快的方法：

$$\begin{align} \sum _ {n=1}^{N} \sum _ {m=1}^{M} d(nm) & = \sum _ {n=1}^{N} \sum _ {m=1}^{M} \sum _ {i|n} \sum _ {j|m} [gcd(i,j)=1] \\ & = \sum _ {n=1}^{N} \sum _ {m=1}^{M} \sum _ {i|n} \sum _ {j|m} \sum _ {d|i,d|j} \mu(d)\\ & = \sum _ {i=1}^{N} \sum _ {m=1}^{M} \sum _ {d|n,d|m} \mu(d)d(\frac{n}{d})d(\frac{m}{d})\\ & = \sum _ {d=1}^{N} \sum _ {a=1}^{\lfloor\frac{N}{d}\rfloor} \sum _ {b=1}^{\lfloor\frac{M}{d}\rfloor}d(a)d(b)\\ & = \sum _ {d=1}^{N} (\sum _ {a=1}^{\lfloor\frac{N}{d}\rfloor}d(a)) (\sum _ {b=1}^{\lfloor\frac{M}{d}\rfloor}d(b)) \end{align}$$

可以$O(\sqrt{n})$完成一次计算。

处理1e18大整数除以1e2小整数的问题

由于(long double)的精度无法满足这么大整数除以小整数的除法，因此我们可以采用如下战略：
首先得到大数与小数除法的整数部分，再用大数对小数的模值计算小数部分。

该方法被用在我对'ZJOI2015地震后的幻想乡'一题答案的处理上。

排列计数类DP的处理方式

对于一类Dp问题，通常要求出所有排列的种数。比如3个红球2个绿球组成了排列种数。

可以将每一种排列进行如下的编号(最小表示法)：从左往右数球，看见一个未出现过的颜色的球，若之前出现了$i-1$种颜色，将它编号为$i$。这样，每$m!$种排列对应一种最小表示法，因此最终的答案乘上$m!$即可。

该方法被用在YZOJ10015yyb和树。

区间求交

在一类为题的解决过程中，我们往往会需要求多个区间的交。有时，区间是会分段的，比如“求一条直线与所有已知直线相交”、或luogu U37667。这时，我们可以求补集的并，这个可以用排序完成统计。

剩余系问题与最短路

在剩余系中的一些问题，如求$k$的倍数中各个位数数字和的最小值，可以使用最短路解决。前面的问题的解答复杂度为$O(k)$。其具体方法是，将剩余系中的每个数看成一个节点，然后节点之间存在转移的边，意为已经有一个剩余系中的某个数，要获得另一个数的代价。然后从初始数字到终止数字的最短路就是答案。

前面的问题可以使用如下的方式建立$O(k)$的图。将一个数字乘$10$,将一个数字加$1$。

积性函数线性筛

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

证明：

$$\begin{aligned} (F*G)(ab) & =\sum_{d|ab}F(d)G(\frac{ab}{d})\\ & =\sum_{d|a,p|b}F(dp)G(\frac{ab}{pd})\\ & =\sum_{d|a,p|b}F(d)F(p)G(\frac{a}{d})G(\frac{b}{p})\\ & =(\sum_{d|a}F(d)G(\frac{a}{d}))(\sum_{d|b}F(d)G(\frac{b}{d}))\\ & =F(a)G(b) \end{aligned}$$

因此，积性函数卷积可以线性筛，积性函数点积显然也可以线性筛。

对于线性筛的函数，一般有如下处理方式：

• 1.找$F(a\times p)$在$p|a$与$p\not|a$情况下的取值。
• 2.求出$F(p^k)$，利用函数的积性求出$F(\Pi p_i^{k_i})$

或者可以

• 1.对于每个$a$，找到$p^k|a$，其中$p$为$a$最小的质因子
• $F(a)=F(a/p^k)F(p^k)$，不难证明在线性筛时$F(a/p^k)$和$F(p^k)$都已经筛出来了，因为它们的最小质因子都不超过$p$，而线性筛保证每个数被自己的最小质因子筛到，且按照递增顺序筛。

一类有决策单调性的Dp

dp有决策单调性，可以用cdq分治将时间复杂度优化为状态数的$\log N$倍。

用函数$f(L, R) = [l, r]$定义一个区间的转移区间，状态$[L, R]$的转移区间为$[l, r]$。

则，如果我们将区间$[L,R]$的中点的转移点算出来，那么$[L,mid)$和$(mid,R]$的转移区间的无交并将是$[l,r]$，这样，递归二分$[L,R]$至多$\log N$层，每一层的区间即转移区间都恰好构成区间$[1,N]$。因此总复杂度将是$N\log N$。

如果转移方程$f[i]=f[j]+g(j+1,i)$中的$g$难以计算，但是可以方便地像莫队一样维护，我们可以在递归的过程中维护$g$,不难发现递归的每一层，左右端点移动的总次数不会超过$4N$(大概)，因此复杂度不变。

应该不存在更难转移的$g$了。更简单的$g$一般可以用前缀和、线段树等维护。

双栈排序

双栈排序指用两个栈和入栈、出栈两个操作，对一个排列排序。

两个元素不能放入同一个栈当且仅当：存在$i<j<k,a[k]<a[i]<a[j]$

1.$n\leq 2000$，dp找出不能在一个栈中的元素对，然后判断是否“不能在同一个栈中”的关系组成二分图。

2.$n\leq 2\times 10^5$，将二分图模型转成更普适的2-SAT模型，然后用可持久化线段树优化连边过程。空间复杂度 $O(n\log n)$，时间复杂度 $O(n\log n)$。且空间复杂度常数较大，$10^5$数据大约需要$300MB$空间。

3.只求出第一种做法中的二分图的一个生成树进行二分图染色，然后用类似第二种方法的一种方法判断是否可行，即所有可以连的边的两端的点颜色不同。求生成树可以用线段树动态维护某个点左边的所有联通块的编号，每次用线段树取出最大编号和最小编号的可行点，启发式合并它们的联通块。这样的时间复杂度$O(n\log^2n)$，空间复杂度$O(n)$。且时空复杂度常数都很小，因此整体上优于第二种方法。

4.同第三种方法，但是将所有元素映射到二维平面上，一个点需要与一个左侧无界的矩形区域内的所有点连边。按照一定顺序扫描可以保证这个矩形区域的右侧不降，下方不降，这样线段树就有点多余了，只需要用堆就可以了。

5.还可以使用并查集维护，时间复杂度$O(n\alpha(n))$，见http://uoj.ac/submission/332724

统计平方、方差的手段

方差=平方的平均数-平均数的平方

因此统计方差是建立在统计和、平方和的基础上的。

对于一类问题：如求所有子矩阵内点数的平方和，可以利用这种方法：一个集合内点数的平方和可以表示为一个集合内点对的个数。

统计不包含任何一个点/至少包含一个点的子矩阵个数

设k为点数：

$O(k^2)$方案：枚举每个“包含至少一个点的子矩阵”包含的最左边的点，然后用更左边的点限制矩阵的上下边界。

SAM中fail树层次遍历序的轻松获得

利用等价类最长长度进行基数排序，得到的就是层次遍历序，因为fail树父亲的长度短于儿子。但是不适用于广义SAM。

树上包含根的联通块计数类问题

可以转化为对偶图

如果不要求包含根，可以用点分治

不支持在线的数据结构的在线化

可以采用二进制分组，用$\log n$个这样的数据结构替代一个大的可在线的数据结构。每当后一个数据结构大于前一个，就暴力合并这两个数据结构。

采用时间线段树可以支持时间区间询问。

有关同余的数学问题的解法

有两种思路，第一种基于复杂度分析，找到问题的分界点，当某个数的权值在$\sqrt{n}$上下时分别采用不同的方法。第二种是构造递归结构处理，如BZOJ1421，求$L\leq xD\mod M\leq R$的最小$x$。

有关图的连通性的题

1.可以枚举1所在的子集(或者枚举一个有代表性的子图，比如竞赛图中拓扑序最小的强连通分量)
2.可以花Bell数的时间枚举划分，然后斯特林容斥

以x为第一关键字，以y为第二关键字的最优化问题

将x乘上很大的权值与y相加，然后做单关键字最优化。

可以类比到凸优化问题。可以处理$kx+by$的最优化问题。

判断一条边在不在XXX内

最大匹配：观察这条边能否通过一个环将自己的流量转移到别的地方。跑完最大匹配后tarjan求出强连通分量，看这条边的两个端点是否在同一个强连通分量内。如果不在，则它必在最大匹配内，反之不一定在。也可以从未匹配点开始DFS，将所有可能通过增广路交换虚实的边打上标记，这些边可以出现在最大匹配内。剩下的边中的匹配边一定出现在最大匹配内。

最大权匹配：删边重做。

最大生成树：它负责连接的两个联通块间是否有同样权值的边。

查询被两个东西同时覆盖的元素个数：同时维护$x+y$和$x^2+y^2$，如CF-gym-102028

枚举拆分法

一些题目可能可以通过暴力枚举整数的拆分解决，其特征是对称性较强、等价情况较多、数据范围$50$左右。

如：BZOJ4671异或图，BZOJ1478Isomorphism

动态线性基：

方法1：时间线段树(需要离线)，复杂度带一个 $\log$

方法2：维护线性基的每个基向量是由哪几个原始向量组成的，每次删除一个向量，找出这个向量参与的基向量中最高位最低的一个，用这个向量异或其它被删除向量参与的基向量。现在其余的向量里都没有了这个被删除向量，并且线性基结构没有发生改变。现在只需要修改最高位最低的那个向量，再将其重新插入线性基即可。复杂度没有$\log$

状态压缩DP减少空间复杂度的技巧

由于一般的状态压缩dp的转移是一个分层图，只会存在相邻层之间的转移，我们不妨将每一层的状态拿出来单独保存，这样可以将空间复杂度从$O(2^n)$降低至$O(\binom{n}{n/2})$。

tarjan对拓扑排序的替代

tarjan后的编号即为拓扑序的反序。

形态不变的树的一个转化技巧

如SPOJ-QTREE6，可以将自己连向父亲的边的颜色设为自己的颜色。

用SAM可以$O(cn)$构建后缀数组

实测在随机数据下比基数排序树状数组慢一倍左右，但是卡树状数组数据下性能稳定，可以比树状数组快至少$20\%$

计数类问题的一些技巧

• 1.括号序列法：
  
  • 将序列问题转化为括号序列问题。因为很多序列问题都满足“匹配”、“前缀为正”等常见的性质。这样，可以转化为括号序列问题进行计数。
  • 一般来说，如果采用Dp的形式计数，我们会用$f[i][j]$中$i$表示前$i$位，$j$表示前缀和。这样两维的限制就可以满足“匹配”、“前缀为正”的性质。
  • 如：Left Most Ball (ARC002F)，Permutation and Minimum (AGC030F)
• 2.二次统计法
  
  • 如果需要维护二次方和，一般有两种常见套路：
  • a.将二次方和用一次方和转移，即$(x+1)^2=x^2+2x+1$，只需要分别维护展开后的每一项，就可以转移。
  • b.将二次方拆成点对计数。比如说一段区间的“贡献”是平方，即在区间内放两个求的方案数。如Placing Squares (AGC013E)
• c.更复杂的问题也可以这样，比如51nod1947

一个有意思的对偶

将一个数拆分为$k$个数的方案，等价于拆分成不超过$k$的数。这两个问题可以用五边形数或者Dp求解。其中Dp方法为分块Dp。

另外，将一个数拆分为不超过$k$的不重复数字，等价于拆分成不超过$k$个连续数字。这两个问题可以用Dp求解。方法是：$f[i][j]$表示拆分为不超过$k$的不重复数字，前$i$个数和为$j$的方案数，其中$i\leq \sqrt{n},j\leq n$，支持两个转移：将所有数加$i$，或者将所有数加$i$，再最前面添$1$。注意当最后一个数大于$k$的时候需要容斥掉这个情况，即$f[i][j]=f[i-1][j-i]+f[i][j-i]-f[i-1][j-(k+1)]$

在线段树上一个区间内二分

一般的线段树上二分只针对整个线段树区间。如果需要在一个特定的区间内二分，找到“最靠右的满足某条件的值”，可以先像普通询问一样找到log个可能区间，在最右边的一个可能区间内二分。时间复杂度依旧是$O(\log n)$