自用问题总结

数学概率/期望

经典期望问题

一个人走路,有$p$的概率走一步,$1-p$的概率停下,问期望走多少步。

共有三种解法,第一种: 最经典的期望求解法。 $$\sum_{i=1}^{\infty} 总共走了i步的概率*i$$

$$=p+2(1-p)p+3(1-p)p^2+\cdots$$

第二种: 直接对从$i\rightarrow i+1$这步出现的概率进行统计。 $$\sum_{i=1}^{\infty} 走第i步的概率$$

$$= p+p^2+p^3+\cdots$$

第三种: 令事件的期望为$E(x)$。则得方程: $$E(x)=0(1-p)+p(E(x)+1)$$

像是递归一样的东西...可以解得: $$\Rightarrow E(x)=\frac{p}{1-p}$$

ps:(此处也是期望递推方程的设计方法之一:LP4550)

上面三种都可以规约成这种形式。

是不少期望的原始形式。

Min-Max容斥

令$max(S)$为集合$S$中的最大值,$min(S)$为最小值,则有:$$max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)$$

推论:$$E(max(S))=\sum_{T\subseteq S}(-1)^{|T|-1}E(min(T))$$

一个常用的概率公式

$$\sum \limits_{i=0}^{k} iP(x=i)= \sum \limits_{i=0}^{k} P(x\geq i)$$

以上为离散形式。在积分形式下仍然适用。

期望解题技巧杂集

  • 设定好状态与期望方程
  • 数据范围较小考虑爆搜
  • 如果出现了小范围后效性可以考虑用待定系数法消除后效性(LP3251)

并查集按秩合并

即把深度浅的接到深度深的,可以做到$\log n$的复杂度。
按秩合并和路径压缩一起用可以做到常数级复杂度。
在可持久化并查集中,按秩合并较为重要。

Floyd传递闭包

跟Floyd思想差不多,即设计dp方程枚举中转点,状态$f_{i,j}$表示$(i,j)$是否联通。 复杂度是$O(n^3)$的。

线段树相关

线段树区间加法/开方/求和

原题:UOJ228

在updata的时候加入两个特判:如果$max_x=min_x$则打一个区间减法tag代替开方,如果$max_x-\sqrt{max_x}=min_x-\sqrt{min_x}$则手法相同,否则继续递归。

复杂度非常玄学。

线段树维护最大流

原题:CF903G
转化成最小割,公式分析。

散点有限次数区间修改

原题:CF438D
当散点的更改次数有上限时,可以用线段树剔除已达到更改次数的点

线段树维护直径

原题:https://oj.changjun.com.cn/problem/detail/pid/2553
对于树上直径有定理,两棵子树中的点构成的直径的端点一定是子树中的端点,因此可以转化为区间问题分治。

区间中位数的维护

原题:LP2839

二分答案。然后将$< x$的数改为$-1$,其余改为$1$。则区间中位数$\geq x$等价于区间和$\geq 0$。

关于树状数组套主席树

事实上套的不是主席树。由于我们在树状数组上设的节点所包含的主席树已经跟其它节点没有任何形式的关联,所以我们可以直接把主席树改成动态开点线段树,能节省不少空间。

博弈论

SG函数

设一局ICG游戏有若干局面。
若某一局面没有下一局面可以移动,则称该局面为Terminal Position。
称先手必输局面为P-Position,先手必赢局面为N-Position。
显然Terminal Position为P-Position。

设局面有SG函数$SG(x)$,则$SG(x)=0$时,$x$为P-position。对于任意局面存在$SG(x)=mex(SG(v))$,当且仅当$v$属于$x$的子局面。

扩展:Multi-SG

Min-Max 搜索 (极大极小搜索)

考虑轮流执子。先手开始出发形成局面的搜索树,对每一个最终局面估价。那么后手会让能达到的局面的权值尽量小,先手会让能达到的局面的权值尽量大。从底层往上递推,先手能够选择一条在这样情况下能够达到的最优解。

例题见[一双木棋chess]。

C++11下更好的rand函数

#include<chrono>
#include<random>
...
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // 64bit mt19937_64
...
uniform_int_distribution<int>(l,r)(rng); // 返回l到r中的一个随机整数
shuffle(a.begin(), a.end(), rng); // randome_shuffle替代

组合数学相关

Catalan数 $C_n$

$$C_n=\frac{1}{n+1}\binom {2n} {n}=\frac{(2n)!}{(n+1)!n!}$$ $$C_n=\sum \limits _{i=0}^{n-1} C_{i}C_{n-1-i}$$ $$C_n=\binom{2n}{n}-\binom{2n}{n-1}$$ $$C_n=\frac{2(2n-1)}{n+1}C_{n-1}$$

一些结论: $C_n=n$个点的无序号二叉树个数

二项式反演

$$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$$ $$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$$ $$a_k=\sum\limits_{i=k}^n{i\choose k}b_i\Rightarrow b_k=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}a_i$$

Prufer序列

https://www.cnblogs.com/zwfymqz/p/8869956.html

$n$个点的无向图的有标号生成树个数:$n^{n-2}$

多项式相关

FFT

还是要弄清FFT分治的到底是个什么东西,以及分治到底部是个什么东西。

FWT

正向变换: $$\text{xor: } \text{tf}(A)=< A_0+A_1, A_0-A_1>$$

$$\text{and: } \text{tf}(A)=< A_0+A_1, A_1>$$

$$\text{or: } \text{tf}(A)=< A_0, A_1+A_0>$$

反向变换: $$\text{xor: } \text{utf}(A)=\left< \frac{A_0+A_1}{2},\frac{A_0-A_1}{2}\right>$$

$$\text{and: } \text{utf}(A)=< A_0-A_1,A_1>$$

$$\text{or: } \text{utf}(A)=< A_0,A_1-A_0>$$

正向变换的$or$等价于求子集和。

牛顿迭代运算总结

求解关于多项式$B(x)$的方程:$F(B(x))\equiv 0 \pmod {x^n} $

假设有$F(B_0(x))\equiv 0 \pmod {x^{\left \lceil \frac{n}{2} \right \rceil}}$

将$F(B(x))$在$B_0(x)$处进行泰勒展开可得: $$B(x)\equiv B_0(x)-\frac{F(B_0(x))}{F'(B_0(x))} \pmod { x^n }$$

多项式开方

$$\sqrt{A(x)}=F(x)$$

$$\Rightarrow G(F(x))=F(x)^2-A(x)\equiv 0 \pmod {x^n}$$

牛顿迭代求解$F(x)$即可。

其它运算类似,详见YYB的博客

原根的求法

令模数$p$有唯一分解$p-1=\prod {p_i}^{k_i}$,则$g$是$p$的原根当恒有$g^{\frac{p-1}{p_i}}\neq 1$。

多项式求逆代替多项式分治

https://www.cnblogs.com/NaVi-Awson/p/9254631.html

怎么好像还能优化复杂度的...

子集卷积

求:$$f_S=\sum \limits_{T\subseteq S} g_Sh_{T-S}$$

等价于求:$$f_S=\sum \limits_{A\cup B=S, |A|+|B|=|S|}g_Ah_B$$

那么我们对$g, h$新增以子集大小为关键字的维度,对于$g_{i,S}$,若$|S|\neq i$则置$0$。$h$同理。每次要求$f$在第$i$维的多项式,我们就将$g, h$分别在$j,i-j$维的多项式做一次或卷积并将卷得的多项式全部相加,然后再将$f$在$i$维的不符合条件的项置$0$。

子集卷积常见于状压dp的优化。对于类似像地震后的幻想乡的dp优化,需要钦定某个最小的值出现在我们需要转移过来的状态,那么我们有个很直接的想法就是某个最小的值没有出现过在那个状态里就直接安排掉。可是你说这个最小值在不同的状态下是不同的,我么考虑我们最终需要的信息是全集,而全集需要转移过来的状态一定包含最小值也就是第一个元素,所以我们可以直接钦定所有的状态都必须包含第一个元素,否则不合法,这样转移过来的值就是正确的了。

莫比乌斯反演相关

两种形式

形式A:$g(x)=\sum_{d|x}f(d)$ $f(x)=\sum_{d|x}\mu(\frac{x}{d})g(d)$

形式B:$g(x)=\sum_{x|d}^{n}f(d)$ $f(x)=\sum_{x|d}^{n}\mu(\frac{d}{x})g(d)$

定理

$$\sum_{d|n}\mu(d)=\begin{cases} 1 \quad n=1 \\ 0 \quad n>1 \end{cases}$$

推论: $$[gcd(i,j)==1]=\sum_{d|gcd(i,j)}\mu(d)=\sum_{d|i,d|j}\mu(d)$$

动态规划相关

斜率优化

若$f_i$可以从$f_j, j< i$转移过来并且能够换成如下形式$y=kx+b$,其中$y,x$为与$j$相关的值,$k,b$为与$i$相关的值且$k$为定值,$b$一般包含$f_i$,我们要使$f_i$最大或最小就等价于使$b$最大最小。因此我们维护$y,x$为与$j$相关的决策点,将由$k$决定的直线上移或下移,碰到的第一个点就是我们要的最优的决策转移。

为此我们需要维护有关于$x,y$的上/下凸包,决策点会从这个凸包中决出。

一般使用单调队列即可,但如果询问的$k$没有单调性,则需要在凸包中二分。如果凸包加入的坐标没有单调性,则使用平衡树/CDQ分治来维护凸包。分治就是将分治出的所有的凸包中的每个最优决策点取出,并在这些决策点中再得到一个决策点。

manacher

字符串中间加入特殊字符避免奇偶性讨论。

假设有回文中心$mid_i$和回文半径$r_i$,记$\max \limits_i mid_i+r_i-1=mr$,对于这样的$i$,我们考虑枚举现在求$j>i$的回文中心,那么我们易知其回文中心的下限可以从以$mid_i$对称过来,再进行暴力扩展,之后再更新$mr$。

这样的算法是线性的。

计算几何相关

最小圆覆盖

https://enceladus.blog.luogu.org/solution-p1742

挺神仙的,但是三点定圆太麻烦了...

模板代码

本文链接:https://acxblog.site/archives/problems.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。