[关闭]
@Cyhlnj 2019-04-06T12:33:45.000000Z 字数 119281 阅读 3059

退役前的部分记录/计划

Cyhlnj算法总结
Myblog

注意!!!

ios :: sync_with_stdio(false);
用了这个后只能 cin,cout,不然会

Contest online

AtCoder(Yahoo Programming Contest 2019)
A
个选前两个贪心
B
判断是否是一条链
C
如果 那么只进行操作一
否则先凑足 个,每次换完钱后再换饼干
D
这场比赛最难的题目?
假设枚举了一个起点和终点
那么 之间的贡献就是其间 为奇数的个数,可以转化为前缀和的形式
考虑 向左或 向右走的贡献
同样的枚举一个边界,贡献就是边界之外的 加上边界内的偶数()的个数,算上 的贡献,这个都可以预处理,都是前(后)缀相减取 的形式
最后枚举 ,也是前(后)缀相减取 的形式,乱搞搞就行了
E
枚举一个行的集合,如果这些行中有 个列的异或和为 个列的异或和为
那么列的选择方案就是
只需要统计异或和不为 的行向量集合个数
即总方案 异或和为 的行向量集合个数,线性基即可
F
不难发现序列第 个可以是前 个人手中的球
只需要 个的序列,剩下的组合数即可

Codeforces Global Round 1
A
模拟即可
B
总长度减去前 大的间距
C
,那么一定能找到一个数字 使得
否则,,输出 的最大因子
D
记录这每个数字的个数,
表示从小到大的第 个数字,这个数字还有 个,上一个有
理论上 ,一个位置能出的不同顺子最多三种,如果 ,那么一定有一种出了三次,直接拆开每个出三连即可
考场上写到了9
E
这个变换在差分数组上表现为相邻两个数的交换,直接判断即可
F
在线就是维护每个点到所有点的距离,主席树存储,两遍 预处理,空间有点卡
直接离线存储询问一起 就行了
G
官方题解
首先黑点不会获胜,如果黑点获胜,那么白点一定可以在按照黑点获胜的策略在之前获胜
考虑如果没有选过的点的做法,分情况讨论
1. 存在一个度数大于 的点,显然白点
2. 存在一个度数大于 的,且有大于 个非叶子的相邻点的点,还是
3. 剩下的情况就是一些度数为 的点,以及不超过两个的度数为 的点有大于一个叶子的相邻点的点,不难发现这种情况只有当点数为奇数的时候才会
4. 其它情况均为
考虑有选过的点怎么办,题解里面把这样的点变成了四个没有被选过的点
懒得放图片就描述一下中间一个点,然后周围挂三个点,选挂的三个点中任意一个为原来的点连回原图
这样为什么是对的呢,因为在双方绝顶聪明的时候,白的选了原来的点,黑的就一定会选中间的那一个,如果黑的再次选一个点,那么白的可以拿走剩下的点,状态不变
H
首先如果合法的串不多就是一个简单的 自动机 +
考虑到自动机上有很多状态是存在所有转移的,也就是数位 ,第一个满足 的地方
把所有这样的前缀加入 自动机,最多
表示从 点开始,任意再选 个能得到的合法串的个数
这样就把那些没有新建的状态的贡献加上了

Codeforces Round #545 (Div. 1)
T1
对于每行每列分别离散化,求出大于这个位置的数字的个数即可。
T2
每次选择当前串的最长的 接上去即可
T3
拆点,对于一个点 ,拆成 ,在原图中如果有边 则连边
可以发现如果 能到 ,那么 也一定能到达
所以 要么在同一个强连通分量里,要么不在同一条直链上。
所以直接缩点 即可。
T4
判环法,一个人 一次 步,另一个人 一次 步。
走了 步, 走了 步。
不难发现 ,而 是一次 步,所以 一定没有走完一个环,所以只要再次走 步就可以刚好到了终点。
其它的点也是一样。
总步骤
T5
不难发现每次加的一些 只要保留第一个就行了。
一操作很好做,直接扔掉前面的信息即可。
考虑二三操作,可以想到用单调队列来维护。
假设 ,那么一次三操作 变得小于 的条件显然是
,所以维护一个 的斜率单调递增的下凸壳即可。
T6
首先可以以最后烧掉的点为根,变成有根树。
考虑一次 操作的影响,设原来的根为 ,那么会使得 这条链的顺序变成 烧到 并且是最后烧的链,其它点相对顺序不变。
现在问题是怎么统计每个点在它之前的点的个数。
可以把 操作看成是一种区间(链)覆盖一个新的最大编号,然后换根。
那么一个点的排名就变成了小于等于它的编号的点个数减去它祖先编号和它相同的点的个数。
这种染色问题可以用 维护, 就直接 ,同一个编号的点一定在一棵 中,直接覆盖即可。
外加一个树状数组维护小于等于它的编号的点个数。

数学

导数积分表

导数


积分

各种东西

牛顿二项式


其中

MR素数测试

大整数分解/Pollard Rho

ExLucas

意义下的值

那么就只要求出模 的值,然后 合并即可
考虑求


1. 首先可以把分子分母中 的因子约分
的个数为

2. 提出 后,就只要求出 就好了,逆元也可以直接
先把 中含有 这个因子的项单独拿出,那么

对于 之前提出来算过了,所以递归处理后面的就好了
考虑前面的求法,
由于是模 意义下的,所以这些东西被分成若干段相乘,每段值一样,直接预处理即可

  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. namespace IO {
  5. const int maxn((1 << 21) + 1);
  6. char ibuf[maxn], *iS, *iT, c;
  7. int f;
  8. char Getc() {
  9. return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
  10. }
  11. template <class Int> void In(Int &x) {
  12. for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
  13. for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);
  14. x *= f;
  15. }
  16. }
  17. using IO :: In;
  18. const int maxn(1e6 + 5);
  19. int mod, p[20], a[20], x[20], b[20], num, fac[maxn];
  20. inline int Pow(ll x, ll y, int m) {
  21. ll ret = 1;
  22. for (; y; y >>= 1, x = x * x % m)
  23. if (y & 1) ret = ret * x % m;
  24. return ret;
  25. }
  26. inline void ExGcd(int a, int b, int c, int &xx, int &yy, int m) {
  27. if (!b) {
  28. xx = (c / a + m) % m, yy = 0;
  29. return;
  30. }
  31. ExGcd(b, a % b, c, yy, xx, m);
  32. yy = (yy - 1LL * (a / b) * xx % m + m) % m;
  33. }
  34. inline ll Gcd(ll a, ll b) {
  35. return !b ? a : Gcd(b, a % b);
  36. }
  37. inline ll F(ll xx, int yy) {
  38. return xx < yy ? 0 : xx / yy + F(xx / yy, yy);
  39. }
  40. int ans, cur, xx, yy;
  41. inline int Inv(int a, int m) {
  42. return ExGcd(a, m, Gcd(a, m), xx, yy, m), xx;
  43. }
  44. inline int Fac(ll n, int pi, int xi) {
  45. return n <= pi ? fac[n] : 1LL * Pow(fac[xi], n / xi, xi) * fac[n % xi] % xi * Fac(n / pi, pi, xi) % xi;
  46. }
  47. ll n, m;
  48. inline ll Solve(int pi, int ai, int xi) {
  49. ll nn = F(n, pi) - F(m, pi) - F(n - m, pi);
  50. if (nn >= ai) return 0;
  51. nn = Pow(pi, nn, xi);
  52. int facn = Fac(n, pi, xi), im = Inv(Fac(m, pi, xi), xi), inm = Inv(Fac(n - m, pi, xi), xi);
  53. return 1LL * facn * im % xi * inm % xi * nn % xi;
  54. }
  55. int main() {
  56. In(n), In(m), In(mod), cur = mod, fac[0] = 1;
  57. for (int i = 2; i * i <= cur; ++i)
  58. if (cur % i == 0) {
  59. p[++num] = i, x[num] = 1;
  60. while (cur % i == 0) cur /= i, ++a[num], x[num] *= i;
  61. }
  62. if (cur > 1) p[++num] = cur, ++a[num], x[num] = cur;
  63. for (int i = 1; i <= num; ++i) {
  64. for (int j = 1; j <= x[i]; ++j)
  65. if (j % p[i]) fac[j] = 1LL * fac[j - 1] * j % x[i];
  66. else fac[j] = fac[j - 1];
  67. b[i] = Solve(p[i], a[i], x[i]);
  68. }
  69. for (int i = 2; i <= num; ++i) {
  70. int xx, yy, c = b[i] - b[1], lcm = x[1] * x[i];
  71. ExGcd(x[1], x[i], c, xx, yy, lcm);
  72. b[1] = (1LL * xx * x[1] % lcm + b[1]) % lcm, x[1] = lcm;
  73. }
  74. printf("%d\n", b[1]);
  75. return 0;
  76. }

伯努利数(坑)(重要)

拉格朗日乘数法(坑)

拉格朗日反演(坑)




扩展

杨氏矩阵(坑)

集合幂级数(坑)

线性插值(坑)

N/二次剩余

N次剩余

给定 ,且 最好为质数
可以算出 的解
首先可以算出 的原根
解方程 ,这个直接

那么 ,这个直接
无解在 的时候判掉,最后快速幂得到答案

二次剩余

的一个解 ,其中 为一个奇素数
1. 有二次剩余的条件


证明
首先有
若存在一个解 ,那么
所以

2. 算法一
如果 的原根,且 那么解就是
证明
结合上面的条件,有
因为 ,那么 一定为偶数
可以在 的复杂度内找到解
3. 算法二
随机一个数字
使得 不存在二次剩余,期望次数为
定义一个新的数域,设 (类似于 )
那么所有的数都可以表示为 的形式
根据有解的条件可以得到

所以
定理
证明
二项式定理展开得到
显然除了第 项和第 项的组合数不是 的倍数
那么就是
由于
那么得到

这就好了,因为
所以
现在只要证明 不存在 项就好了
假设
那么
所以 或者
如果 ,那么
因为 没有二次剩余,而 显然有二次剩余
所以 没有二次剩余,矛盾
得到
总结一下
第一步随机一个 ,使得 不存在二次剩余
第二步直接重载运算求出 的二次剩余

单纯型法(坑)

类欧几里德算法

类欧几里得算法的推导Cyhlnj

形式上类似于欧几里得算法,把 转化成 可能就是是类欧几里得算法的精髓

Catalan数

,卡塔兰数满足递归式:
(其中 )


第二类斯特林数

一类求解 的方法
  1. 二项式展开,通常合并的复杂度为
  2. 斯特林展开,通常是要计算 ,可以递推 转移。

表示 个球放进 个无标号的盒子内,要求盒子不为空的方案数
1. ,其中
2. ,其中
3. ,其中
4.
结论


的球放在 个不同的盒子内没有无空盒限制的方案数,枚举不是空的的盒子)
公式

可以容斥得到
转简得到

第一类斯特林数

表示 个不同元素,分成 个圆,排列的方案数
那么
显然有


结论

证明
一个排列对应一个置换
把这个置换中的上下对应位置连边,可以得到许多的环
由于排列和置换是一一对应的,所以我们要求排列的个数,就是求用n个元素组成环的方案数,所以我们枚举环的个数
它的生成函数


nlogn倍增

那么
考虑利用 推出

那么



所以可以反转之后

bell数

的集合划分数,显然是第二类斯特林数的前缀和


即枚举 的划分

BurnSide&Polya

置换个数 等价类个数 不动点数

Tarlor展开

斐波拉契数列的性质Cyhlnj






扩展欧拉定理

原根

定义
两种
1.对于一个数的最小正整数,那么就称的原根
2.假设一个数对于来说是原根,那么的结果两两不同,且有 ,那么可以称为是的一个原根
性质

求法

求模原根的方法:对素因子分解

若恒有成立,则就是的原根

容斥

反演




下面的直接带入到上面


如果 ,那么 之间是能够反演的
都是下三角矩阵, 就是单位矩阵
知道这个就可以矩阵求逆打表了,而且你发现直接求逆是

二项式反演

证明



单位根反演

不能丢!!!


证明:
,那么

否则,等比数列求和

如果能快速求出某个多项式的点值,那我们就可能能求出 的特定倍数幂的系数和。
形式化的,我们可以求

带入到所求的东西中去





stirling反演

把第一类Stirling数看成无符号的

第一类Stirling数幂与下降幂的关系

第二类Stirling数幂与下降幂的关系

反转公式

证明



那么

另外一个同理

Min-Max容斥以及kthmax扩展

证明
考虑一种第 大值被作为最小值计算的次数

kthmax
求第 大元素
构造容斥系数
使得


考虑第 大值被作为最小值计算的次数

它应该等于


二项式反演得到

那么

X X
X
X
X X

(数字即为满足要求的, 为对角线)

显然, 为一组, 为一组
两两互不干扰,每一组相当于是不能同时选两个相邻的位置(组中)
然后就可以 出 忽略 个,有 个满足要求的方案
这样再乘上 就可以算出 表示至少有 个位置满足要求的排列方案
要算出恰好 个的,然而答案不是 (虽然看上去很对)

因为 个受了限制,另外 个没有限制的也会有满足要求的情况
这样就导致一种情况被算了多次,并且显然在 个的时候和 的时候被重复算的次数不同

假设 表示恰好有 个位置满足要求的排列方案
那么
因为每一种恰好 个的被算了

数论分块

计数小trick

WC2019

对于求恰好 个的方案数,并且贡献为 的形式
可以利用二项式定理展开

含义为枚举所有的集合 ,如果 是答案的子集,那么贡献为 ,否则为
所有子集 的贡献之和恰好是
这样可以省去容斥

组合数

prufer编码

Matrix
1. 给定一棵带标号的无根树,找出编号最小的叶子节点,写下与它相邻的节点的编号,然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止
2. 注意到,如果一个节点A不是叶子节点,那么它至少有两条边;但在上述过程结束后,整个图只剩下一条边,因此节点A的至少一个相邻节点被去掉过,节点A的编号将会在这棵树对应的Prüfer编码中出现。反过来,在Prüfer编码中出现过的数字显然不可能是这棵树(初始时)的叶子。于是我们看到,没有在Prüfer编码中出现过的数字恰好就是这棵树(初始时)的叶子节点。找出没有出现过的数字中最小的那一个(比如④),它就是与Prüfer编码中第一个数所标识的节点(比如③)相邻的叶子。接下来,我们递归地考虑后面n-3位编码(别忘了编码总长是n-2):找出除④以外不在后n-3位编码中的最小的数(左图的例子中是⑦),将它连接到整个编码的第2个数所对应的节点上(例子中还是③)。再接下来,找出除④和⑦以外后n-4位编码中最小的不被包含的数,做同样的处理……依次把③⑧②⑤⑥与编码中第3、4、5、6、7位所表示的节点相连。最后,我们还有①和⑨没处理过,直接把它们俩连接起来就行了。
为什么不全部删除呢
根据上面的东西,显然前 个点就可以找出最后剩下的两个点了
那么长度为 的最后两个是唯一确定的
所以长度为 的序列可能存在有不合法的情况

结论

  1. 一个点会在 序列中出现度数
  2. 一些大小为 的连通块生成树方案数为 ( 为连通块数, 为点数)
    证明:
    的每一位需要从 中枚举,所以方案数是
    从块内不同点连出去一样是不同的方案,对于每个被删除时联通块,需要乘以联通块内的点数
    最后两个连通块的边的方案数也是
    所以就是

    • 明明的烦恼
      序列中度数为 的点会出现

      答案就是

    • 树的计数
      上面的弱化版。。

    • 小猴打架
      计数模板

    • 文艺计算姬
      答案就是
      证明:
      中的数字出现 次, 中出现 次,根据 解码可知, 中的数字和内部顺序确定了,那么它们的相对位置也可以确定
      证明:
      构建基尔霍夫矩阵,去掉第一行第一列,发现分成四个部分
      左上角 ,主对角线为 ,其余为
      右下角 ,主对角线为 ,其余为
      左下右上都是
      手动求行列式
      把第 行加上前 行,变成


      再加上后 行,变成

      依次加到前 行中,变成了下三角
      对角线上有

其它

待完成

矩阵(坑)

线性代数(坑)

线性代数基础知识
线性代数

矩阵变换与行列式

第一类初等变换(换行换列)使行列式变号
第二类初等变换(某行或某列乘k倍)使行列式变k倍
第三类初等变换(某行(列)乘k倍加到另一行(列))使行列式不变

行列式

定义

对于一个 的矩阵 ,选出一个长度为 的排列 ,设其逆序数为

求法
  1. 上三角或下三角或高斯约当后的主对角线的乘积
  2. 行列式与它的转置行列式相等
  3. 若行列式的某一行每一个元素都可以由两个数相加得到,则这个行列式是对应两个行列式的和

行列式展开

对于 ,矩阵 删除 行和 列的结果
代数余子式:
那么

伴随矩阵


那么有

矩乘

求逆

把矩阵 的右边放一个单位矩阵,然后把左边高斯约当成单位矩阵,此时右边就是
如果不能高斯约当成单位矩阵则无解

特征多项式(坑)

求矩阵的特征多项式

Cayley-Hamilton定理

是数域 上的一个 矩阵,
的特征多项式,则

基尔霍夫矩阵

它实际上是这么个鬼玩意儿。。。
其任意一个代数余子式是所有生成树的边权积的和。。。

由于是边权三进制不进位的相加,那么可以考虑每一位的贡献
对于每一位,生成树的边权相当于是做模 意义下的加法
考虑最后每一种边权的生成树个数,这个可以直接用生成函数,在矩阵树求解的时候做一遍这个生成函数的模 意义下的循环卷积求出系数即可
暴力多项式运算不可取
考虑选取 个数字 ,使得
即找出 次单位复数根
这个直接带入三角表示法即可得到
把这些东西带入,矩阵树定理求出点值,最后手动 即可

待完成

反演/筛

一般积性函数筛法

为积性函数
首先
然后考虑线性筛,一个质数
,那么 的最小质因子
假设它的指数为 ,那么
那么当
否则就只要能快速求出 就好了

结论

  1. 小的与互质的数的和为,特判,互质的数成对存在

直接莫比乌斯反演得到:


杜教筛筛 的前缀和
然后后面的东西暴力算(分块)的复杂度是

莫比乌斯反演

区间筛

杜教筛

min_25筛

求解积性函数 的前缀和


做法
首先假设
为从小到大的第 个质数

为质数或最小质因子
求解
,则不存在 以内的合数的最小质因子大于
那么
否则,,考虑从 推过来
显然 中多了最小质因子为 的那些合数的贡献,设为
设这些合数为 ,贡献即
要满足这些合数的最小质因子为 要满足最小质因子
提出 ,所以 小于 的质数的贡献
也就是
(因为 以内为质数或最小质因子 的只有质数)
总结一下就是

求解前缀和
为质数
假设 的最大的数
那么
再设 的最小质因子
分成两个部分计算
1. 为质数,贡献即为
2. 为合数:
枚举最小质因子 及其的指数 (这里的 不是一个)
贡献为

首先积性函数的性质有前面的一部分

而这样就没有算到 的贡献,加回来即可
答案就是

其它筛

多项式

FFT

DFT

IDFT


证明


直接等比数列求和发现就是

算法



考虑分治


那么

那么

而根据折半引理可以得到

都是 项的,所以用上面的东西只能处理出 的值
考虑计算

根据消去引理和折半引理可以得到

弄成这样就已经可以计算了,但是我们精益求精
注意到 ,所以还可以化简

总结一下就是

这就是所说的蝴蝶操作
最后把 补成 的形式就可以了

Rader排序

递归常数大,所以搞个非递归
考虑上面不断的分组分治最后会是什么样子
设一共有 个位置,考虑第 次分组,定义二进位顺序为从低到高
分到左边的一定是二进制的第 位为
分到右边的一定是二进制的第 位为
而左边和右边的位置的编号个个数都是 ,这就使得
左边的位置的编号二进制的第 位为
左边的位置的编号二进制的第 位为
这样看来最后的每个位置 ,它上面的数字的二进制一定是 的二进制表示反转过来的

有了 就可以先换好位置,然后每一层对应的 一定是一段连续的区间
这样就可以快速定位从而方便的实现非递归

NTT

在模 意义下 的原根


展开可证明

牛顿迭代


泰勒展开后

拉格朗日插值

若给出点值

多项式除法

已知次多项式次多项式
除以的商及余式
也就是




取模

表示把系数倒置,即前后
那么可以多项式求逆,再相乘得到
然后去掉带入原式相乘再相减得到

个变量的幂和

问题描述
个变量 ,求所有的






考虑这个 是个什么

等比数列求和可证
那么就有两种方法
方法一

就是

那么分治 然后求 再 求导即可
方法二

把它积分一下

那么



那么分治 然后求 即可
还有一只 的做法,见 博客

多项式多点求值


给定一个多项式
求出对于每个点
考虑分治


那么
对于

对于

分治下去
可以类似线段树把 储存下来
分治就是在 线段树,每次只要取模就好了
复杂度为大常数

多项式插值


给出 个点 ,求出这个多项式
根据拉格朗日插值


先考虑如何对于 求出


那么就是要求

根据洛必达法则

所以只要求出 然后多点求值就好了
所以现在要求

这部分仍然可以分治得到


那么上面的就是

分治即可
不过常数实在是太大了...

常系数线性递推

求一个满足 阶齐次线性递推数列 的第


给出 以及
级别,
它的特征多项式为

如果 不是很大,可以直接对于 求逆得到
否则
设向量
的转移矩阵为
那么
引入Cayley-Hamilton定理
看成 带入 中,有 (全 矩阵)
所以有

如何求
显然P(x)=C(x)
写出来


根据定义 为单位矩阵
那么

按照最后一列展开得到

所以只要多项式倍增快速幂 取模就好了(听起来就慢)
最后

所以有

计算即可
注意多项式倍增快速幂的时候取模的多项式是一样的,可以预处理出它的逆

FWT

对于一种集合运算 ,求
一个很 的想法就是构造一种变换以及它的逆变换,使得能像 一样弄,这个东西就是

或卷积


构造
(即 的子集的 和)
显然
(这里指的是按数组相同下标相乘)
现在考虑求 以及它的逆变换

考虑分治计算,把 数组按照二进制为分成 两部分,设为
假设我们算出了
相当于一个的二进制的第 位为 ,一个为
那么 就是 (表示数字拼接, 指的是按数组相同下标相加)
缺少的 的子集由 得到。

同样考虑分治,假设我们算出了
显然
多余的 的子集由 扣除。

与卷积


构造
(即 的母集的 和)

???
与/或卷积不就是个高维前缀和吗???
好有意思啊。。。

异或卷积


mmp异或打不出
构造

表示 二进制下 的个数姑且这么叫着吧
是不是很鬼畜?
如果你想要问我是怎么弄出来的那我就只能orz了
你发现它也是满足 (类似于容斥)

优化卷积和一些套路

生成函数

抄题解
,随便做一下,设 为相同的边的个数,输出
,给定其中一棵树
设初始答案为 ,首先可以发现,每有一条边和给定的树相同就会使得答案除去
那么可以利用矩阵树定理,已经有的边权值为 ,其它的连成完全图,权值为
求解行列式之后乘上 即可,
第一种正解 即可 不会
第二种正解

一个小trick
对于求恰好 个的方案数,并且贡献为 的形式
可以利用二项式定理展开

含义为枚举所有的集合 ,如果 是答案的子集,那么贡献为 ,否则为
所有子集 的贡献之和恰好是 ,这样可以省去容斥

那么可以直接算 在每一种两棵树都包含的边集 的贡献
下面的 默认为
对于一种边集 ,假设它把图分成了 个连通块,每个连通块大小为
运用 的知识,不难得到其生成树的方案数为
直观上来看这个东西,只能得到一个 表示 所在连通块,大小为
然后考虑 的组合意义,即从每一个连通块选出一个点的方案数
那么就可以把上面的 改成 表示 所在连通块是否选择了一个点
树形 即可
,同样的利用那一个trick
表示钦定 条边相同的方案数
那么
考虑计算 ,还是直接利用 ,容易得到


(含义参考:分配标号,连通块之间无序)


根据这个式子不难得到一个 ,枚举划分
继续推导,直接代到答案里面,可以得到


可以写成生成函数的形式

代入



忽略与 无关项,就是

这个东西直接写成无穷项的形式不会影响答案,不难发现就是

多项式 即可

循环卷积

求出模 意义下的循环卷积
考虑插值出最后多项式,类比 的方法
假设我们要求


为多项式
我们知道了 个点值


那么

而根据消去引理
所以

正好对应了循环卷积,所以只要求得到 的点值就可以得到最后的多项式了

Bluestein's algorithm(坑)

待完成

数据结构

LCT题目

李超线段树题目与知识

线段树维护一次函数,以x为值域,比较交点的上下,每个点存储一个最大/最小的那个线段
递归处理(一些类似标记永久化的东西)

长链剖分题目

生成树题目

虚树题目

线段树

  1. void Update(int rt, int o, int l, int r, int mx) {
  2. if (l == r) {
  3. tr[rt].ans = min(tr[rt].ans, max(tr[o].mx, mx) + l);
  4. return;
  5. }
  6. register int mid = (l + r) >> 1;
  7. if (tr[o << 1 | 1].mx >= mx) { //直接更新,递归右边
  8. tr[rt].ans = min(tr[rt].ans, tr[o].ans);
  9. Update(rt, o << 1 | 1, mid + 1, r, mx);
  10. }
  11. else { //右边取端点,递归左边
  12. tr[rt].ans = min(tr[rt].ans, mid + 1 + mx);
  13. Update(rt, o << 1, l, mid, mx);
  14. }
  15. }

第二种点最多 个,所以还是维护最小值 的个数

Segment Tree Beats

二维

即线段树套线段树
注意每个点维护的是矩阵的整体的信息
1. 当前外层树节点是叶节点
修改这个外层树节点所对应的内层树,由于是单点修改,找到内层树叶节点时,直接修改。
2. 当前外层树节点不是叶节点
修改这个外层树节点所对应的内层树,同理找到内层树叶节点,但是不能直接修改,而是要从当前外层树的儿子所对应的内层树的相同的叶节点更新上来

fhqtreap/可持久化题目

  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. namespace IO {
  5. const int maxn((1 << 21) + 1);
  6. char ibuf[maxn], *iS, *iT, c;
  7. int f;
  8. char Getc() {
  9. return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
  10. }
  11. template <class Int> void In(Int &x) {
  12. for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
  13. for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);
  14. x *= f;
  15. }
  16. }
  17. using IO :: In;
  18. const int maxn(1e5 + 5);
  19. int ch[2][maxn], fix[maxn], val[maxn], size[maxn], trash[maxn], top, tot, rt;
  20. inline int NewNode(int v) {
  21. int x = top ? trash[top--] : ++tot;
  22. fix[x] = rand(), val[x] = v;
  23. ch[0][x] = ch[1][x] = 0, size[x] = 1;
  24. return x;
  25. }
  26. inline void Update(int x) {
  27. size[x] = size[ch[0][x]] + size[ch[1][x]] + 1;
  28. }
  29. int Merge(int x, int y) {
  30. if (!x || !y) return x + y;
  31. if (fix[x] > fix[y]) {
  32. ch[1][x] = Merge(ch[1][x], y), Update(x);
  33. return x;
  34. }
  35. else{
  36. ch[0][y] = Merge(x, ch[0][y]), Update(y);
  37. return y;
  38. }
  39. }
  40. void Split(int x, int k, int &l, int &r) {
  41. if (!x) l = r = 0;
  42. else {
  43. if (val[x] <= k) l = x, Split(ch[1][x], k, ch[1][l], r), Update(l);
  44. else r = x, Split(ch[0][x], k, l, ch[0][r]), Update(r);
  45. }
  46. }
  47. int x, y, z;
  48. inline void Insert(int v) {
  49. Split(rt, v, x, y), rt = Merge(Merge(x, NewNode(v)), y);
  50. }
  51. inline void Delete(int v) {
  52. Split(rt, v, x, y), Split(x, v - 1, x, z);
  53. rt = Merge(Merge(x, Merge(ch[0][z], ch[1][z])), y);
  54. trash[++top] = z;
  55. }
  56. inline void Rank(int v) {
  57. Split(rt, v - 1, x, y);
  58. printf("%d\n", size[x] + 1);
  59. rt = Merge(x, y);
  60. }
  61. inline int Kth(int o, int v) {
  62. while (true) {
  63. if (size[ch[0][o]] + 1 == v) return val[o];
  64. else if (size[ch[0][o]] >= v) o = ch[0][o];
  65. else v -= size[ch[0][o]] + 1, o = ch[1][o];
  66. }
  67. }
  68. inline void Pos(int rk) {
  69. printf("%d\n", Kth(rt, rk));
  70. }
  71. inline void Pre(int v) {
  72. Split(rt, v - 1, x, y);
  73. printf("%d\n", Kth(x, size[x]));
  74. rt = Merge(x, y);
  75. }
  76. inline void Suf(int v) {
  77. Split(rt, v, x, y);
  78. printf("%d\n", Kth(y, 1));
  79. rt = Merge(x, y);
  80. }
  81. int main() {
  82. srand(time(NULL));
  83. int n, op, v;
  84. for (In(n); n; --n) {
  85. In(op), In(v);
  86. if (op == 1) Insert(v);
  87. else if (op == 2) Delete(v);
  88. else if (op == 3) Rank(v);
  89. else if (op == 4) Pos(v);
  90. else if (op == 5) Pre(v);
  91. else Suf(v);
  92. }
  93. return 0;
  94. }

可持久化就是每次分裂/合并的时候都记录一下节点即可

  1. inline void Copy(int x, int y) {
  2. fix[y] = fix[x], size[y] = size[x], val[y] = val[x];
  3. ch[0][y] = ch[0][x], ch[1][y] = ch[1][x];
  4. }
  5. int Merge(int x, int y) {
  6. if (!x || !y) return x + y;
  7. if (fix[x] > fix[y]) {
  8. int p = ++tot;
  9. Copy(x, p), ch[1][p] = Merge(ch[1][p], y), Update(p);
  10. return p;
  11. }
  12. else{
  13. int p = ++tot;
  14. Copy(y, p), ch[0][p] = Merge(x, ch[0][p]), Update(p);
  15. return p;
  16. }
  17. }
  18. void Split(int x, int k, int &l, int &r) {
  19. if (!x) l = r = 0;
  20. else {
  21. if (val[x] <= k) l = ++tot, Copy(x, l), Split(ch[1][l], k, ch[1][l], r), Update(l);
  22. else r = ++tot, Copy(x, r), Split(ch[0][r], k, l, ch[0][r]), Update(r);
  23. }
  24. }

线段树分裂(坑)

可能和 分裂类似

可持久化堆(坑)

可持久化可并堆

什么鬼。。。不就是可持久化线段树合并。。。

猫树

空间
预处理时间
查询
做法,在线段树的每个点 保存一个
表示 的信息和和 的信息和
那么每次查询 只要知道 即可
表示去掉不同的位置
那么查询 即可

替罪羊树

Euler-Tour Tree(坑)

支配树(坑)

块状树(坑)

灭绝树(坑)

杂题

  1. inline void Merge(int u, int v) {
  2. for (int i = 0; i < c[u]; ++i) {
  3. int l = 0, r = -1;
  4. for (int j = i; j <= m; j += c[u]) {
  5. while (l <= r && (j - q[l]) / c[u] > d[u]) ++l;
  6. if (l <= r) Cmax(f[u][j], f[v][q[l]] + (j - q[l]) / c[u] * w[u]);
  7. while (l <= r && f[v][j] - j / c[u] * w[u] >= f[v][q[r]] - q[r] / c[u] * w[u]) --r;
  8. q[++r] = j;
  9. }
  10. }
  11. }
  12. inline void Max(int u, int v) {
  13. for (int i = 0; i <= m; ++i) Cmax(f[u][i], f[v][i]);
  14. }
  15. void Solve(int u, int ff, int tp) {
  16. for (int e = first[u], v; ~e; e = edge[e].next)
  17. if ((v = edge[e].to) != ff && v != son[u]) Solve(v, u, 0);
  18. if (son[u]) Solve(son[u], u, 1);
  19. for (int i = son[u] ? dfn[son[u]] - 1 : ed[u]; i >= dfn[u]; --i) {
  20. if (i != ed[u]) Merge(id[i], id[i + 1]);
  21. Merge(id[i], 0);
  22. if (i != dfn[u]) Max(id[i], id[ed[id[i]] + 1]);
  23. }
  24. for (int j = 0; j <= m; ++j) Cmax(ans, f[u][j]);
  25. if (!tp) {
  26. for (int i = dfn[u]; i <= ed[u]; ++i)
  27. for (int j = 0; j <= m; ++j) f[id[i]][j] = inf;
  28. }
  29. }

待完成

贪心

待完成

分治

点分治

边分治

对于一条边,算经过这条边的路径的答案
点分治不方便的就是同一棵子树的容斥,而边分治不用考虑
直接边分治显然菊花就卡掉了
所以我们要转二叉树
具体来说就是把一个点的儿子建一棵线段树,添加虚拟节点,点权为其父亲的点权,只有线段树的叶子节点有边权

  1. int Build(int val, int l, int r) {
  2. if (l > r) return 0;
  3. if (l == r) return tmp[l];
  4. int mid, ls, rs, cur;
  5. mid = (l + r) >> 1, cur = ++n, w[cur] = val;
  6. ls = Build(w[cur], l, mid), rs = Build(w[cur], mid + 1, r);
  7. if (ls) Add2(cur, ls, ls <= m);
  8. if (rs) Add2(cur, rs, rs <= m);
  9. return cur;
  10. }
  11. void Rebuild(int u, int ff) {
  12. int e, v, mid, ls, rs;
  13. len = 0;
  14. for (e = head[u]; ~e; e = edg[e].next)
  15. if ((v = edg[e].to) != ff) tmp[++len] = v;
  16. mid = (len + 1) >> 1;
  17. ls = Build(w[u], 1, mid), rs = Build(w[u], mid + 1, len);
  18. if (ls) Add2(u, ls, ls <= m);
  19. if (rs) Add2(u, rs, rs <= m);
  20. for (e = head[u]; ~e; e = edg[e].next)
  21. if ((v = edg[e].to) != ff) Rebuild(v, u);
  22. }

二分答案

线段树分治

二进制分组

分治

二进制

最大最小值分治

CDQ

搜索

dancing links(坑)

meet in the middle

搜索

分块/暴力

块状链表(坑)

貌似是一些块用链表维护,核心思想为分裂和合并

回滚莫队

  1. 对于不方便添加的,想办法变成只有删除的
  2. 对于不方便删除的,想办法变成只有添加的

先只考虑 1,把询问按照左端点的块排序,相同则右端点从大到小
每次先把左端点放在块的最左边,右端点单调,只需要每次暴力删除左边,得到答案之后再滚(还原)回去即可

套路

如果一个题目你发现直接询问空间小时间大,而暴力预处理空间大时间小。
你可以考虑分块,大于 暴力查询,小于的暴力更新(预处理)

图论

预流推进(坑)

zkw费用流(坑)

ISAP(坑)

结论

二分图最小点覆盖/最大独立集/最长反链

最大独立集和最小点覆盖互为补集

最小点覆盖
先最大匹配
每次从左边找到一个未匹配点增广(假的增广,显然增广不了,因为已经是最大匹配)
然后标记点
最后左边没有标记过的点和右边标记过的点就是最小点覆盖
伪证:因为一条假的增广路一定是左边的点作为开头和结尾的,所以选右边的就能覆盖这个假的增广路

最长反链
最大独立集就是最长反链可能,猜的
去掉这些最小点覆盖就是要找的最长反链

二分图匹配的可行边/必须边

先用 求任意一组最大匹配,然后建一张新图:
匹配边 连边
非匹配边 连边
匹配的左点
不匹配的左点
匹配的右点 ,
不匹配的右点,
然后用 求强连通分量
是可行边的条件:
是匹配边或者 在同一个 里。
即残量网络
伪证:
每找到一个环,就说明可以根据环的方向退流+增广得到一组新的匹配。

你发现不在同一个 里的匹配边就是必须边。

最小割的可行边/必须边

在残余网络上跑 求出所有
为点 所在 的编号
显然有 (否则 有通路,能继续增广)

图的欧拉定理


为点数, 为边数, 为平面区域数

Hall定理

二分图 中,,当且仅当 中任意 个顶点都与 中至少 个点相邻时,该二分图存在完美匹配

Landau's Theorem

一个长度为 的序列 ,是合法的比分序列当且仅当:

时这个式子必须取等号。
或者倒过来和下面一样

无向图的三元环计数

将边定向,由度数小的点指向大的,相同则指向编号大的
枚举每条边,将所有 与相连的点打上标记,再枚举与 相连的点,如果有标记则算进答案

每个点的出度都小于等于
证明:对于度数小于 的点显然,度数大于 的点出度一定指向度数大于 的点,而度数大于 的点不超过 个,所以每个点的出度都小于等于

可以保证是个有向无环图。
为什么呢,要想定向存在环,则这个环上的点度数必须相同,由于保证了编号从小到大走
所以是不可能存在环的。

复杂度

二分图匹配

最小点覆盖

用最少的点让每条边都至少和其中一个点关联。
最少点覆盖数 最大匹配数

最小路径覆盖

用尽量少的不相交的简单路径覆盖有向无环图所有顶点
最小路径覆盖数 节点数 二分图的最大匹配
证明:
每有一个匹配,就有两条路径的合并
即所需路径减 ,那么答案就是

二分图的最大独立集

选择最多的顶点,使得所选择的点集中任意两点之间没有连边
二分图的最大独立集 = 点数 二分图最大匹配数
证明:
即删掉最少的点使得剩下的点没有边相连,即 最小点覆盖

二分图的最大团

圆方树

KM题目

直径

网络流

最小割树

算法
初始时把所有点放在一个集合
从中任选两个点出来跑原图中的最小割
然后按照 集合与 集合的归属把当前集合划分成两个集合,递归处理
这样一共跑了 次最小割
可以证明图中任意一对点之间的最小割的数值都包含在这 个数值当中
把每次求出的最小割看成是两个点之间的边,可以建出一棵树

定理1
任意三点之间的最小割一定是两个相等的较小值和一个较大值

证明
设任意三点 之间的最小割分别为
是这三者中的最小值
那么在做 割时, 一定属于其中的某一个集合,设其与 同属于一个集合
那么就有
又因为 ,所以两者相等

定理2
图中至多只有 种不同的最小割

证明
编了一个构造的证明
首先根据定理 ,可以转化成如下问题:

个点的无向完全图,要给每一条边染色,要求每个三元环上有两条边同色,求最多可以染多少种颜色

考虑归纳法
假设现在已经有一条长度大于 的链 上的边的颜色互不相同
考虑染 这条边
如果链长 ,那么 只能选择链上某条边的颜色
如果链长 ,假设两个端点在链上的不是 的边的颜色都是链上某条边的颜色
那么取出其中两条 只能选择两个中其中一条边的颜色,即链上某条边的颜色

所以可以得到,颜色互不相同的边不能形成环,所以最优的显然是树,即 中颜色

上下界网络流

模拟费用流

看代码清晰的多QwQ

  1. if (!hole.empty()) {
  2. ans += (v = -hole.top().first + x[i]);
  3. id = hole.top().second, mouse.push(make_pair(x[i] + v, 0));
  4. hole.pop();
  5. if (id) hole.push(make_pair(y[id], id));
  6. while (!hole.empty() && -hole.top().first + x[i] < 0) {
  7. ans += (v = -hole.top().first + x[i]);
  8. id = hole.top().second, hole.pop();
  9. hole.push(make_pair(x[i], 0));
  10. if (id) hole.push(make_pair(y[id], id));
  11. }
  12. }
  13. else ans += inf, mouse.push(make_pair(x[i] + inf, i));
  14. mouse.push(make_pair(x[i], i));
伪ZKW费用流
  1. inline int Bfs() {
  2. int e, u, v;
  3. memset(dis, 63, sizeof(dis));
  4. memset(vis, 0, sizeof(vis));
  5. dis[T] = 0, vis[T] = 1, Q.push(T);
  6. while (!Q.empty()) {
  7. u = Q.front(), Q.pop();
  8. for (e = first[u]; ~e; e = edge[e].next)
  9. if (edge[e ^ 1].f && dis[u] - edge[e].w < dis[v = edge[e].to]) {
  10. dis[v] = dis[u] - edge[e].w;
  11. if (!vis[v]) vis[v] = 1, Q.push(v);
  12. }
  13. vis[u] = 0;
  14. }
  15. return dis[S] != dis[T + 1];
  16. }
  17. int Dfs(int u, int maxf) {
  18. if (u == T) return maxf;
  19. vis[u] = idx;
  20. int ret = 0, &e = cur[u], v, f;
  21. for (; ~e; e = edge[e].next)
  22. if (dis[v = edge[e].to] + edge[e].w == dis[u] && edge[e].f && (vis[v] ^ idx)) {
  23. f = Dfs(v, min(maxf - ret, edge[e].f));
  24. ret += f, edge[e].f -= f, edge[e ^ 1].f += f;
  25. if (ret == maxf) return ret;
  26. }
  27. if (!ret) dis[u] = dis[T + 1];
  28. return ret;
  29. }
  30. inline int MCMF() {
  31. int ret = 0, f, sum = 0;
  32. while (Bfs()) {
  33. idx = 0;
  34. while (true) {
  35. ++idx, memcpy(cur, first, sizeof(cur));
  36. ret += (f = Dfs(S, 1e9)) * dis[S], sum += f;
  37. if (!f) break;
  38. }
  39. }
  40. return sum == flow ? ret : -1;
  41. }

一般图最大权匹配(坑)

详见国家集训队 by cyb

并查集

(最短/长)路径/DAG

生成树/重构树

Tarjan

欧拉回路

Hamilton

  1. void Hamilton() {
  2. int l = que[1], r = l;
  3. for (int i = 2; i <= len; ++i) {
  4. int cur = que[i];
  5. if (lnk[cur][l]) nxt[cur] = l, l = cur;
  6. else if (lnk[r][cur]) nxt[r] = cur, r = cur;
  7. else {
  8. for (int k = 0, j = l; j; k = j, j = nxt[j])
  9. if (lnk[cur][j]) {
  10. nxt[k] = cur, nxt[cur] = j;
  11. break;
  12. }
  13. }
  14. }
  15. r = 0, vis[l] = 1;
  16. for (int i = nxt[l]; i; i = nxt[i])
  17. if (!vis[i]) {
  18. if (r) {
  19. for (int j = i; j; j = nxt[j]) {
  20. int flg = 0;
  21. for (int k = r, lst = l; ; lst = k, k = nxt[k]) {
  22. if (lnk[j][k]) {
  23. if(j != l) nxt[l] = r;
  24. nxt[lst] = i, flg = 1;
  25. l = j, r = k;
  26. break;
  27. }
  28. if (k == l) break;
  29. }
  30. if (flg) {
  31. for (int k = i; ; k = nxt[k]) {
  32. vis[k] = 1;
  33. if (k == j) break;
  34. }
  35. break;
  36. }
  37. }
  38. }
  39. else if (lnk[i][l]) r = l, l = i;
  40. vis[i] = 1;
  41. }
  42. for (int i = 1; i <= len; ++i) vis[que[i]] = 0;
  43. nxt[l] = r, len = 0;
  44. }

2-sat

其它

待完成

博弈论

各种博弈(坑)(重要)

1. Bash Game

基本问题
有一堆石子,总个数是 ,两名玩家轮流在石子堆中拿石子,每次至少取 个,至多取 个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。
解决方法
如果 则先手必败,否则先手必胜。

2. Wythoff Game

基本问题
有两堆石子,石子数可以不同。两人轮流取石子,每次可以在一堆中取,或者从两堆中取走相同个数的石子,数量不限, 不能不拿,取走最后一个石头的人获胜。判定先手是否必胜。

解决方法
这个东西意义不是很大,打表找规律之后可以发现先手必败的状态一定形如
。其中 表示不大于 的最大整数。

3. Nim Game

基本问题
有三堆石子,两人轮流取,每次可以从一堆中取走任意数量个石子,至少取走一个,取走最后一个石头的人获胜,问先后手谁胜。
一般推广:有 堆石子 ,两人轮流取,每次可以从任意一堆石子中取走至少一个石子,问先后手谁胜。
解决方法
方法很简单,直接求所有
的异或和,如果异或和为 则先手必败,否则先手必胜。

4. k倍动态减法

基本问题
一堆石子共 个,两人轮流拿,不能不拿,要求该轮拿走的石子的个数不能超过上一轮的
数,先手首次操作不能把石子都拿走,取走最后一个石头的人获胜

k=1
当石子的个数是 时先手必败,否则先手必胜

k=2
当石子的个数是斐波那契数列中的元素时先手必败,否则先手必胜

5. Nim&Bash Game

基本问题
一共 堆石子,每次每人可以从任意一堆中拿走 个石子,取走最后一个石头的人获胜

解决方法
对每堆石子 后异或和为 则先手必败,否则先手必胜

6. Nim k Game

基本问题
一共 堆石子,每次每人可以从最多 堆中拿走任意多石子,不能不拿,取走最后一个石头的人获胜

解决方法
把每堆石头的数量二进制拆开,对每位分别求和,若每一位上的和都是 的倍数则先手必败,否则先手必胜

7. 阶梯博弈

基本问题
级阶梯上每级有若干个石头,每次操作可以从任意级阶梯把任意多石头移动到下一级阶梯(移动第一级的石头相当于丢掉),不能不移,不能操作者输

解决方法
计算奇数级阶梯的异或和,为 先手必败否则先手必胜

8. Anti-SG 问题

SJ 定理:
对于一个 Anti-SG 游戏,如果我们规定当前局面中所有单一游戏的 SG 为 0,游戏结束。那么先手必胜的条件就是:
1. 游戏的 SG 值不为 0,且存在一个单一游戏的 SG 值大于 1。
2. 游戏的 SG 值为 0,且不存在一个单一游戏的 SG 值大于 1。

题目

待完成

DP

决策单调性题目与知识(坑)

蒟蒻的理解:
首先要满足每个决策的区间右端点单调

DP套DP题目

插头DP题目

子集DP题目

动态dp题目

树形dp题目

状压dp题目

其它+dp

单调队列优化

  1. In(n), In(w);
  2. for (int i = 1, s, nw, v; i <= n; ++i) {
  3. In(s), In(nw), In(v);
  4. for (int j = 0; j < nw; ++j) {
  5. int l = 0, r = -1;
  6. for (int k = j; k <= w; k += nw) {
  7. while (l <= r && (k - q[l]) / nw > s) ++l;
  8. while (l <= r && f[q[r]] - q[r] / nw * v <= f[k] - k / nw * v) --r;
  9. q[++r] = k;
  10. if (l <= r) Cmax(g[k], f[q[l]] + (k - q[l]) / nw * v);
  11. }
  12. }
  13. for (int j = 0; j <= w; ++j) f[j] = g[j];
  14. }
  15. int ans = 0;
  16. for (int i = 0; i <= w; ++i) Cmax(ans, f[i]);
  17. printf("%d\n", ans);

数据结构优化

NTT/FFT/插值优化

矩阵乘法优化

凸优化

期望概率题目

神奇结论?

对于 之间的随机变量 ,第 小的那个的期望值是
对于 之间的随机变量 的概率是 的时候成立, 不知道
排列的计数问题可以转化成 之间的随机变量的概率问题,因为两个数相同的概率为 .

斯坦纳树

斯坦纳树是这样一类问题:带边权无向图上有几个点是关键点,要求选择一些边使这些点在同一个联通块内,同时要求所选的边的边权和最小。
为什么不能直接求解最小生成树,因为会有边相交的情况

待完成

字符串

trie

KMP

exkmp

  1. id = 1, mx = 0;
  2. for(RG int i = 2; i <= n; ++i){
  3. if(i <= mx) lcp[i] = min(lcp[lcp[id] - mx + i], mx - i + 1);
  4. while(i + lcp[i] <= n && s[lcp[i] + 1] == s[lcp[i] + i]) ++lcp[i];
  5. if(lcp[i] + i - 1 > mx) id = i, mx = lcp[i] + i - 1;
  6. }

最小循环表示法

  1. for(RG int i = 1; i <= n; ++i) s[i] = s[n + i];
  2. RG int m = n << 1, i = 1, j = 2;
  3. while(i <= n && j <= n){
  4. RG int len = 0;
  5. while(s[i + len] == s[j + len] && i + len <= m && j + len <= m) ++len;
  6. if(s[i + len] > s[j + len]) i += len + 1;
  7. else j += len + 1;
  8. if(i == j) ++j;
  9. }

Suffix_Array

  1. RG int m = 30;
  2. for(RG int i = 1; i <= n; ++i) ++t[rk[i] = s[i] - 'a' + 1];
  3. for(RG int i = 1; i <= m; ++i) t[i] += t[i - 1];
  4. for(RG int i = n; i; --i) sa[t[rk[i]]--] = i;
  5. for(RG int k = 1; k <= n; k <<= 1){
  6. RG int l = 0;
  7. for(RG int i = n - k + 1; i <= n; ++i) tmp[++l] = i;
  8. for(RG int i = 1; i <= n; ++i) if(sa[i] > k) tmp[++l] = sa[i] - k;
  9. for(RG int i = 0; i <= m; ++i) t[i] = 0;
  10. for(RG int i = 1; i <= n; ++i) ++t[rk[tmp[i]]];
  11. for(RG int i = 1; i <= m; ++i) t[i] += t[i - 1];
  12. for(RG int i = n; i; --i) sa[t[rk[tmp[i]]]--] = tmp[i];
  13. swap(rk, tmp), rk[sa[1]] = l = 1;
  14. for(RG int i = 2; i <= n; ++i) rk[sa[i]] = Cmp(sa[i - 1], sa[i], k) ? l : ++l;
  15. if(l >= n) break;
  16. m = l;
  17. }
  18. for(RG int i = 1, h = 0; i <= n; ++i){
  19. if(h) --h;
  20. while(s[i + h] == s[sa[rk[i] - 1] + h]) ++h;
  21. st[0][rk[i]] = h;
  22. }
  23. for(RG int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  24. for(RG int j = 1; j <= lg[n]; ++j)
  25. for(RG int i = 1; i + (1 << j) - 1 <= n; ++i)
  26. st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

SAM

  1. IL void Extend(RG int c){
  2. RG int np = ++tot, p = last; last = np;
  3. len[np] = len[p] + 1;
  4. while(p && !trans[c][p]) trans[c][p] = np, p = fa[p];
  5. if(!p) fa[np] = 1;
  6. else{
  7. RG int q = trans[c][p];
  8. if(len[p] + 1 == len[q]) fa[np] = q;
  9. else{
  10. RG int nq = ++tot;
  11. len[nq] = len[p] + 1, fa[nq] = fa[q];
  12. for(RG int i = 0; i < 26; ++i) trans[i][nq] = trans[i][q];
  13. fa[q] = fa[np] = nq;
  14. while(p && trans[c][p] == q) trans[c][p] = nq, p = fa[p];
  15. }
  16. }
  17. }

PAM

后端插入

  1. IL void Extend(RG int pos, RG int c){
  2. RG int p = last;
  3. while(s[pos - len[p] - 1] != s[pos]) p = fa[p];
  4. if(!son[c][p]){
  5. RG int np = ++tot, q = fa[p];
  6. while(s[pos - len[q] - 1] != s[pos]) q = fa[q];
  7. len[np] = len[p] + 2, fa[np] = son[c][q];
  8. son[c][p] = np;
  9. }
  10. last = son[c][p], ++size[last];
  11. }

前后插入

  1. int n, tot, prel, sufl, son[26][maxn], len[maxn], deep[maxn], fa[maxn], l, r;
  2. ll ans;
  3. char s[maxn << 1];
  4. IL void Init(){
  5. for(RG int i = l; i <= r; ++i) s[i] = 'z' + 1;
  6. for(RG int i = 0; i <= tot; ++i){
  7. len[i] = deep[i] = fa[i] = 0;
  8. for(RG int j = 0; j < 26; ++j) son[j][i] = 0;
  9. }
  10. prel = sufl = 0, tot = 1, fa[1] = fa[0] = 1, len[1] = -1;
  11. }
  12. IL void Extend(RG int pos, RG int c, RG int &last, RG int op){
  13. RG int p = last;
  14. while(s[pos - op * (len[p] + 1)] != s[pos]) p = fa[p];
  15. if(!son[c][p]){
  16. RG int np = ++tot, q = fa[p];
  17. while(s[pos - op * (len[q] + 1)] != s[pos]) q = fa[q];
  18. len[np] = len[p] + 2, fa[np] = son[c][q];
  19. son[c][p] = np;
  20. }
  21. last = son[c][p], deep[last] = deep[fa[last]] + 1, ans += deep[last];
  22. if(len[last] == r - l + 1) prel = sufl = last;
  23. }
  24. int main(){
  25. while(scanf("%d", &n) != EOF){
  26. Init(), l = 1e5, r = l - 1, ans = 0;
  27. for(RG int i = 1; i <= n; ++i){
  28. RG int op = Input();
  29. if(op <= 2){
  30. RG char c; scanf(" %c", &c);
  31. if(op == 1) s[--l] = c, Extend(l, c - 'a', prel, -1);
  32. else s[++r] = c, Extend(r, c - 'a', sufl, 1);
  33. }
  34. else printf("%lld\n", op == 3 ? tot - 1 : ans);
  35. }
  36. }
  37. return 0;
  38. }

hash

后缀平衡树

用平衡树维护每一个后缀的排名
关键在于查询两个后缀的大小
可以用二分加hash,复杂度 插入
或者:
每次前面插入一个字符,先比较两个后缀第一个字符的大小
而后面的大小我们已经在平衡树上维护好了
像这样分配权值

给树上每个子树一个实数权值区间 ,这个点 权值
左子树 右子树

注意删除的时候,左子树 右子树 ,不能是 ,不然会重复甚至颠倒
那么可以做到 比较
只需要选择一个树高 的树(treap/替罪羊树)使得满足精度要求即可

线性求后缀数组(sais)(坑)

待完成

计算几何(巨坑)

点积


为点积。。。
几何解释就是一个向量在另一个向量上的投影的长度

叉积


1. 可以判断一个向量 是否在 的逆时针方向
的逆时针方向(内侧)
2. 面积
其围成的三角形的面积

凸包

极角排序后单调栈求 ()

旋转卡壳

枚举一条边,找到斜率最靠近它的边,

最小圆覆盖

随机增量, 一下
枚举一个点为圆心,看其它的点是否被包含,否则以这两个点为圆的直径,看其它的点是否被包含,选取最大的三角形外切圆

半平面交

求所有向量的内侧的平面
按照斜率排序,相同的就保留最内侧的(叉积)
然后双端队列插入向量
为什么是双端?因为要围成封闭图形,可能使头部弹出
入队条件:尾部的两个向量的交点在该向量的内侧(叉积)
最后记的把首尾相接,继续弹出不合法的
要先弹尾再弹头,不然就GG了!!!

  1. q[++tl] = l[1], q[++tl] = l[2];
  2. for (int i = 3; i <= m; ++i) {
  3. while (hd < tl && Jud(q[tl - 1], q[tl], l[i])) --tl;
  4. while (hd < tl && Jud(q[hd + 1], q[hd], l[i])) ++hd;
  5. q[++tl] = l[i];
  6. }
  7. while (hd < tl && Jud(q[tl - 1], q[tl], q[hd])) --tl;
  8. while (hd < tl && Jud(q[hd + 1], q[hd], q[tl])) ++hd;
  9. q[tl + 1] = q[hd]

三维凸包(坑)

(https://blog.csdn.net/wu_tongtong/article/details/79346196)

首先对其微小扰动,避免出现四点共面的情况
对于一个已知凸包,新增一个点
视作一个点光源,向凸包做射线
可以知道,光线的可见面和不可见面一定是由若干条棱隔开的 将光的可见面删去,并新增由其分割棱与 构成的平面
重复此过程即可

平面的记录

扰动之后各个平面一定是一个三角形,逆时针方向记录三个顶点表示一个面
有点类似右手螺旋定则,右手定则确定的方向指向多边形的外部

叉积


其模长仍然表示以这两个三维向量作为邻边的平行四边形面积
方向符合右手定则,穿过掌心向手内

  1. struct Point3D {
  2. double x, y, z;
  3. inline Point3D(double _x = 0, double _y = 0, double _z = 0) {
  4. x = _x, y = _y, z = _z;
  5. }
  6. inline Point3D operator +(Point3D ad) const {
  7. return Point3D(x + ad.x, y + ad.y, z + ad.z);
  8. }
  9. inline Point3D operator -(Point3D ad) const {
  10. return Point3D(x - ad.x, y - ad.y, z - ad.z);
  11. }
  12. inline double operator ^(Point3D ad) const { //dot
  13. return x * ad.x + y * ad.y + z * ad.z;
  14. }
  15. inline Point3D operator *(Point3D ad) const { //cross
  16. return Point3D(y * ad.z - z * ad.y, z * ad.x - x * ad.z, x * ad.y - y * ad.x);
  17. }
  18. inline Point3D operator *(double ad) const {
  19. return Point3D(x * ad, y * ad, z * ad);
  20. }
  21. inline double Len() {
  22. return sqrt(x * x + y * y + z * z);
  23. }
  24. };
  25. inline double Rand() {
  26. return rand() / (1.0 * RAND_MAX);
  27. }
  28. inline double Disturb(Point3D &a) {
  29. a.x += (Rand() - 0.5) * eps, a.y += (Rand() - 0.5) * eps, a.z += (Rand() - 0.5) * eps;
  30. }
  31. Point3D a[maxn];
  32. struct Surface3D {
  33. int v[3];
  34. inline Point3D Normal() {
  35. return (a[v[1]] - a[v[0]]) * (a[v[2]] - a[v[0]]);
  36. }
  37. inline double Area() {
  38. return Normal().Len() * 0.5;
  39. }
  40. };
  41. Surface3D f[maxn], tmp[maxn];
  42. int n, tot, vis[maxn][maxn];
  43. double area;
  44. inline int Cansee(Point3D x, Surface3D y) {
  45. return ((x - a[y.v[0]]) ^ y.Normal()) > 0;
  46. }
  47. inline void Convex3D() { //Polygon3D
  48. int i, j, k, cnt, v, x, y;
  49. f[++tot] = (Surface3D){1, 2, 3};
  50. f[++tot] = (Surface3D){3, 2, 1};
  51. for (i = 4; i <= n; ++i) {
  52. cnt = 0;
  53. for (j = 1; j <= tot; ++j) {
  54. if (!(v = Cansee(a[i], f[j]))) tmp[++cnt] = f[j];
  55. for (k = 0; k < 3; ++k) vis[f[j].v[k]][f[j].v[(k + 1) % 3]] = v;
  56. }
  57. for (j = 1; j <= tot; ++j)
  58. for (k = 0; k < 3; ++k) {
  59. x = f[j].v[k], y = f[j].v[(k + 1) % 3];
  60. if (vis[x][y] && !vis[y][x]) tmp[++cnt] = (Surface3D){x, y, i};
  61. }
  62. for (j = 1; j <= cnt; ++j) f[j] = tmp[j];
  63. tot = cnt;
  64. }
  65. }
  66. int main() {
  67. int i;
  68. srand(time(NULL)), scanf("%d", &n);
  69. for (i = 1; i <= n; ++i) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z), Disturb(a[i]);
  70. Convex3D();
  71. for (i = 1; i <= tot; ++i) area += f[i].Area();
  72. printf("%.3lf\n", area);
  73. return 0;
  74. }

闵可夫斯基和(坑)

官方定义:两个图形 的闵可夫斯基和
通俗一点:从原点向图形 内部的每一个点做向量,将图形 沿每个向量移动,所有的最终位置的并便是闵可夫斯基和(具有交换律)

利用瞪眼法得,闵可夫斯基和的边是由两凸包构成的
也就是说把两凸包的边极角排序后直接顺次连起来就是闵可夫斯基和
由于凸包的优美性质,直接归并排序就好了
但是需要注意的是可能会有三点共线的情况,于是再扔过去重新求一次凸包就好了

圆的反演变换(坑)

反演中心为 ,反演半径为 ,若经过 的直线经过 ,且 ,则称 关于 互为反演

性质

  1. 一根过 的直线的反形是本身
  2. 一根不过 的直线的反形是一个过 的圆
  3. 一个过 的圆的反形是一根不过 的直线
  4. 一个不过 的圆的反形是一个和该圆关于 位似的圆
  5. 反演不改变相切关系

Pick定理(坑)

定点都是整点的多边形,内部整点数为 ,边界整点数

把每个整点近似地看成一个圆,那么多边形内部的整点所代表的圆全部被算入
多边形边界上的圆被算了一半,顶点上被算了 半角 外角
外角和 度,于是

Simpson积分

首先函数必须收敛


积分是一个用二次函数近似要求函数的东西
上面的东西是由

推导而来
只选取了三个点会有很大的精度误差
所以可以选取一个 每次取出中点处理


的时候就结束
返回

为什么是 我也不知道

  1. inline double Simpson(double l, double r) {
  2. return (r - l) * (F(l) + F(r) + 4.0 * F((l + r) * 0.5)) / 6.0;
  3. }
  4. inline double Calc(double l, double r, double neps, double ans) {
  5. double mid = (l + r) * 0.5, lans = Simpson(l, mid), rans = Simpson(mid, r);
  6. double dx = lans + rans - ans;
  7. if (fabs(dx) < 15.0 * neps) return lans + rans + dx / 15.0;
  8. return Calc(l, mid, neps * 0.5, lans) + Calc(mid, r, neps * 0.5, rans);
  9. }

待完成

其它

Dilworth定理

线性规划(坑)

弦图(坑)

Berlekamp-Massey算法

算法
它可以用来求常系数线性递推的系数,并且可以求出最短的
求出来有什么用呢?
你可以闷声Cayley-Hamilton定理优化递推矩阵快速幂
算法简介:
首先设一个数列 ,我们想要试出其中满足

的最小的 以及对应的系数
考虑增量法构造
1. 首先因为要求 ,所以 都为 显然是满足条件的,所以初始可以就是全
2. 假设有一个长度为 都满足条件,并且 不满足了

我们只要构造出一个长度为 最短的
使得 然后 按位相加就好了
怎么找到呢,实际上我们之前已经存在有一些不满足条件的情况
假设有个

向后移动 位,前面补 ,第 位搞个
这样得到的长度为 再搞个 乘起来就好了
搞出来的 显然就是我们要求的,但是可能不是最短的
万物皆可持久化把之前所有求过的 全部记录下来
然后又搞个 表示第 挂了的位置
最后弄个变量记录一下最短的就好了

随机化tricks

随机映射多随机几百次...

二维RMQ

维护两个方向 的矩阵,查询变成四个相交的矩阵
这个东西可以用来优化最大流连边

Chtholly-tree

线性基

DFA(坑)

启发式合并/分裂

构造/思维 题目

连边的图为原图,和 的为新图
现在已知 的边,求原图的方案数
考虑一个环上的一条链,它还原成原图的环的方法只能是沿着环的逆时针方向插空还原
因为新图的两个相邻点之间只能插入一个点
那么有显而易见的几种无解的情况:
1. 对于一个不属于环上的点,如果有两个及以上的点同时指向它,那么肯定不能还原成原图的环
2. 对于一个属于环上的点,如果有两个及以上的点同时指向它,那么肯定也不能还原成原图的环
3. 如果环上一条链 和环的沿逆时针方向的另一条链的距离小于 的长度,那么无解

考虑计算答案:
1. 对于新图的单个的环,把长度相同的一起 ,每次可以合并两个,或者奇数长度的同构等
2. 对于基环内向树,如果环上一条链 和环的沿逆时针方向的另一条链的距离等于 的长度,那么只有一种方案,否则如果大于,就有两种,因为此时 的靠近环的点可以选择连上逆时针方向的一个点

把这些东西互不影响,乘法原理即可

单调性

递推

分数规划

高维前缀和

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注