CVBB ACM Team technique

technique:bm

Anonymous (anonymous@undisclosed.example.com) — 2020-06-02T21:39:58+0800

Berlekamp-Massey 算法算法介绍设域 $F$ 上有一无限数列 $s_{0},s_{1},\cdots$，我们想要对某个有限的 $n$，找到一个尽可能短的数列 $c_{1},\cdots,c_{L}$，使得 $s_{j}=-\sum_{i=1}^{L}c_{i}s_{j-i}$ 对 $j=L,L+1,\cdots,n-1$ 成立。特别地，若 $L=0$，意味着 $s_{0}=s_{1}=\cdots=s_{n-1}=0$。记 $s_{0},\cdots,s_{n-1}$ 为 $s^{(n)}$，这样的数列 $c$ 称为 $s^{(n)}$ 的递推式。由定义可以看出，任意 $L\ge n$$c$$s^{(n)}$$L$$c$$s^{(n)}$$s^{(n+1)}$$L'$$c'$$s^{(n+1)}$$L'\ge n+1-L$$L'\le n-L$$$ \begin{aligned} s_{n}&=-\sum_{i=1}^{L'}c'_{i}s_{n-i}\\ &=-\sum_{i=1}^{L'}c'_{i}\left(-\sum_{j=1}^{L}c_{j}s_{n…

technique:centroid_decomposition

Anonymous (anonymous@undisclosed.example.com) — 2020-06-11T21:45:16+0800

静态点分治算法简介一种利用分治进行树上路径统计的算法，算法时间复杂度一般为 $O(n\log n)$。算法思想所有路径分为两种，一种是过根结点的，一种是完全在根结点的某棵子树中的。因此可以考虑分治算法，选取一个点将无根树转换为有根树，然后递归处理每个棵以根节点的儿子为根的子树。$\frac n2$$\log n$$O(n\log^{\alpha}n)$$O(n\log^{\alpha+1}n)$$\log$$\text{sz}$$\text{mson}(u)=\max\left(\max\left(\text{sz}\left(\text{son}\left(u\right)\right),\text{tot_sz}-\text{sz}\left(u\right)\right)\right)$$\text{mson}$$O(n)$$\text{tot_sz}$$n$$k$$k$$O(n^2)$$O(n)$$O(n\log n)$$\text{dist}$$k\le 10^7$$10^7$$\text{dist}$$\text{memset}$$\text{vecto…

technique:delaunay_and_basic_voronoi

Anonymous (anonymous@undisclosed.example.com) — 2021-07-12T21:09:48+0800

Delaunay三角剖分三角剖分假设有平面点集 $V$,设 $e$ 表示 $V$ 中两点构成的线段，$E$ 是 $e$ 的集合，平面图 $G=(V,E)$ 是点集的三角剖分且 $G$ 满足下列条件: * 任意两条边除端点外不相交 * 除端点外，边上没有点集中的点$V$$Delaunay$$Delaunay$$V$$Voronoi$$A$$Voronoi$$Voronoi$$V$$Voronoi$$Delaunay$$Voronoi$

technique:finite_two_person_zero_sum_game

Anonymous (anonymous@undisclosed.example.com) — 2021-07-10T00:20:44+0800

有限二人零和博弈设 $A\in\mathbb{R}^{n\times m}$，$X=\{1,2,\cdots,n\}$，$Y=\{1,2,\cdots,m\}$（即 $X$，$Y$ 均为有限集），$X$ 表示玩家 I 的（纯）策略集合，$Y$ 表示玩家 II 的（纯）策略集合。若玩家 I 选择纯策略 $i\in X$，玩家 II 选择纯策略 $j\in Y$，那么玩家 I 将获得 $A_{ij}$ 的收益，玩家 II 将获得 $-A_{ij}$$A$$X^{*}$$Y^{*}$$$ X^{*}=\{\boldsymbol{p}=(p_{1},p_{2},\cdots,p_{n})^{T}:p_{i}\ge0\land\sum_{i=1}^{n}p_{i}=1\}\\ Y^{*}=\{\boldsymbol{q}=(q_{1},q_{2},\cdots,q_{m})^{T}:q_{i}\ge0\land\sum_{i=1}^{m}q_{i}=1\} $$$p_{i}$$i$$\boldsymbol{p}$$\boldsymbol{p}^{T}A\boldsymbol{q}$$\bol…

technique:formula

Anonymous (anonymous@undisclosed.example.com) — 2020-06-10T17:28:26+0800

数学公式常见用法 mathjax 是很强大的！很多时候不需要大家自创格式：向下取整 $\lfloor\frac{a}{b}\rfloor$ 向上取整 $\lceil\frac{a}{b}\rceil$ 高次开方 $\sqrt[3]{n}$ 同余式 $a\equiv b\pmod{c}$ 取模 $a\bmod{b}=c$ 美化公式当括号中内容较大时，使用 \left\right 来使括号同步放缩。$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$$$$\left|\frac{a}{\left|\frac{b}{c}\right|}\right|$$

technique:front_page

Anonymous (anonymous@undisclosed.example.com) — 2021-07-12T18:14:58+0800

知识点 wiki 基础前缀和双指针法数据结构线段树基础线段树合并树套树数学莫比乌斯反演隔板法数论分块 Berlekamp-Massey 算法 Reeds-Sloane 算法多元多项式插值有限二人零和博弈计算几何旋转卡壳 Delaunay三角剖分和Voronoi图基础字符串 AC自动机图论一般图最大权（最大）匹配点分治 LCT 动态规划 dp的优化杂项表达式求值求01矩阵中最大的全为0或1的矩形或正方形模板模板施工中数学公式施工中…

technique:general_matching_weighted

Anonymous (anonymous@undisclosed.example.com) — 2021-07-04T23:03:53+0800

一般图最大权（最大）匹配建议首先搞懂二分图最大匹配、二分图最大权（最大）匹配、一般图最大匹配这几个 special case。另外可以先阅读参考文献，其中 [1] 讲的是最好的。问题描述给定一个带权无向图 $$$u$$y_u$$B$$z_{B}$$uv$$yz_{uv}=y_{u}+y_{v}+\sum_{u,v\in B}z_{B}-w_{uv}$$z$$z$$\delta$$z_{B}$$2\delta$$z_{B},yz_{uv}\ge0$$uv$$yz_{uv}=0$$B$$\frac{|B|-1}{2}$$z_{B}$$y_{u}$$\frac{\max w}{2}$$z_{B}$$0$$yz=0$$S$$\text{free}$$T$$T$$S$$z$$0$$\mathcal{O}(n)$$3$$1$$S/T$$S$$\delta$$T$$\delta$$S$$z$$2\delta$$T$$z$$2\delta$$S$$z\ge0$$\delta>0$$y$$\frac{1}{2}$$\delta$$\frac{1}{2}$$z_{B}\ge0$$z$…

technique:mobius_inversion

Anonymous (anonymous@undisclosed.example.com) — 2020-05-31T16:43:57+0800

莫比乌斯反演积性函数数论函数是一类定义域在正整数上的函数。若对数论函数 $f$，且 $\forall a, b$ 使得 $(a, b) = 1$，都满足 $$ f(ab) = f(a) \cdot f(b) $$ 则称 $f$ 是积性函数。如果条件弱一些，不需要 $(a, b) = 1$ 也有上式成立，则称 $f$ 是完全积性函数。只要 $f$$f$$p$$f(p^a)$$f$$f, g$$$ h(n) = f(n^p) \\ h(n) = f^p(n) \\ h(n) = f(n)g(n) \\ h(n) = \sum _{d \mid n} f(n) g \left(\dfrac nd \right) \\ $$$$ [P] = \begin{cases} 1, &P \text{ is true} \\ 0, &P \text{ is false} \\ \end{cases} $$$\varepsilon(n) = [n = 1]$$\mathrm{id}(n) = n$$n$$1(n) = 1$…

technique:multivariate_interpolation

Anonymous (anonymous@undisclosed.example.com) — 2021-06-27T23:33:47+0800

多元多项式插值不妨设你想插值一个 $m$ 元，次数不超过 $n$ 的多项式。可见至少需要 ${n+m\choose n}$ 项才可能解出所有项的系数。还在想啥，弄到足够多的项解高消去啊什么？你说 $\mathcal{O}({n+m\choose n}^{3})$ 复杂度太高了？那么 Hecht M, Cheeseman B L, Hoffmann K B, et al. A quadratic-time algorithm for general multivariate polynomial interpolation[J]. arXiv preprint arXiv:1710.10846, 2017. 提出了一个 $\mathcal{O}({n+m\choose n}^{2})$…

technique:number_theory_sqrt_decomposition

Anonymous (anonymous@undisclosed.example.com) — 2020-06-10T17:27:29+0800

数论分块简介数论分块的目的是：将有除法下取整的式子，从 $O(n)$ 优化到 $O(\sqrt{n})$。它就是换了一种计数顺序，从纵向计数改为横向计数（Fubini 原理），将 n/d 相同的数打包同时计算。特此说明：以下若未采用公式体写的 n/d，均代表 C 语言中带取整的整数除法，而不是数学意义上的除法。这是由于如果将数学公式除法加取整写入段落，将使得一行过高。$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$$$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\geqslant\left\lfloor\frac{n}{\frac{n}{l}}\right\rfloor=l$$$$\left\lfloor\frac{n}{\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor}\righ…

technique:rot_cal

Anonymous (anonymous@undisclosed.example.com) — 2021-06-24T21:47:49+0800

参考资料

technique:rs

Anonymous (anonymous@undisclosed.example.com) — 2020-06-02T21:40:20+0800

Reeds-Sloane 算法算法介绍 Reeds-Sloane 算法是 BM 算法的拓展，可以处理模任意正整数的递推式。设环 $\mathbb{Z}/m\mathbb{Z}$ 上有一数列 $s_{0},s_{1},\cdots,s_{n-1}$，我们想要找到一个尽可能短的数列 $a_{0}=1,a_{1},\cdots,a_{l}$，使得 $\sum_{i=0}^{l}a_{i}s_{j-i}=0$ 对 $j=l,l+1,\cdots,n-1$ 成立。不妨用多项式的语言来简单地定义一下递推式的长度：设 $a(x)=\sum_{i=0}^{l}a_{i}x^{i}$$S(x)=\sum_{i=0}^{n-1}s_{i}x^{i}$$a(x)S(x)\equiv b(x)\pmod{x^{n}}$$A=(a(x),b(x))$$L(A)=\max\{\deg(a(x)),\deg(b(x))+1\}$$\deg(a(x))\le\deg(b(x))$$a$$0$$m=\prod p_{i}^{e_{i}}$$p_{i}^{e_{i}}$$m$$p^{e}$$\eta=0,1…

technique:template

Anonymous (anonymous@undisclosed.example.com) — 2020-06-02T22:04:24+0800

这里是知识点部分的模板页面，请参照编写，将各部分修改为自己的内容。其中各级标题中用 <> 包围的部分表示替换为具体内容。 <算法名称> 算法简介（可选）本页面给出了知识点 wiki 的基本格式。$$ 1+1=2\Box $$$$ 1+1=2\Box $$$L$$c$$s^{(n)}$$s^{(n+1)}$$L'$$c'$$s^{(n+1)}$$L'\ge n+1-L$$L'\le n-L$$$ \begin{aligned} s_{n}&=-\sum_{i=1}^{L'}c'_{i}s_{n-i}\\ &=-\sum_{i=1}^{L'}c'_{i}\left(-\sum_{j=1}^{L}c_{j}s_{n-i-j}\right) \end{aligned} $$$L'>n-L$$$ \begin{aligned} s_{n}&=-\sum_{j=1}^{L}c_{j}\left(-\sum_{i=1}^{L'}c'_{i}s_{n-i-j}\right)\\ &=-\sum_{j=1}^{L}c_{j}s_{n-j} \end{aligned} $$$c$$s^{(n+1)…