NOT
CF1556G Gates to Another World
***3300** 这种 $2 ^ n$ 和区间，看着就很想套上线段树，事实上是对的。 **引理 1 ：** > 在线段数内同一颗子树内的点可以互相到达。 这个是非常容易验证的，把边画出来就是在一条链上挂若干条横着的链。 然后我们考虑把区间挂上去，然后用**时光倒流**转化为加边。我们发现，我们可以 ......
神秘的 tips
command_block 's tips 证明：找比较显然的，不要找那些坚涩分散的东西。 资源：博客、目录。查别人水表，翻找那些博客。 题：推荐 ATC 物美价廉，还可以问 LGJ，要。 学习方法：慢慢想 or 像我一样天天贺题，积累 tricks 可以薄纱别人。想题方法可以慢慢培养。 停课：三周 ......
算法竞赛中常见trick
本文主体译自 [Collection of little techniques](https://codeforces.com/blog/entry/100910) 并有所删改 前言略 # 1.bitset优化空间 考虑 **DAG上的可达性** ，给定一个 $n$ 个节点和 $m$ 条边的 DAG ......
UNR #7 补题
意识流题解。 ## 那些你不要的 场上写了一个二分答案 + 栈模拟，实在是太蠢了！ 观察到每次一定会删一个奇数位的和一个偶数位的，最后只有一个奇数位的会保留下来，然后就完了。 ## 比特迷宫 场上写了一个乱搞：每 $24$ 个分一块，对于每块跑出一个最优解。然后把相差 $2^k$ 的相同操作不断合并 ......
2023.4.10
太菜了。 #### T1 求 $$\sum_{L\le a\le b\le R}\lbrack b\space mod\space a=b\space xor\space a\rbrack$$ 值域 $1e18$ . 枚举余数能得到 $\lfloor\frac{b}{a}\rfloor=1$ . 那 ......
四边形不等式
写的有点答辩了。 [四边形不等式优化](https://oi-wiki.org/dp/opt/quadrangle/) 最简单的一种： 2D1D的状态转移方程： $$f_{l,r}=\min_{k=l}^{r-1}\{f_{l,k}+f_{k+1,r}\}+w(l,r)$$ 当 $w(l,r)$ 满 ......
高斯消元
[北文](https://www.luogu.com.cn/user/53769) 讲的。 用 $O(n^3)$ 的复杂度求解线性方程组。 $$a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1$$ $$...$$ $$a_{n1}x_1+a_{n2}x_2+...+a_{n ......
类欧几里得算法
手推不难。 [P5170 【模板】类欧几里得算法](https://www.luogu.com.cn/problem/P5170) 求 $$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$$ $$g(a,b,c,n)=\sum_{i=0}^ ......
2023.4.20
### T1 $P$ 是任意一个 $1$ 至 $n$ 的排列，最大化 $$\sum_{i=1}^{n}P_i\space\text{mod}\space i$$ 答案显然 $\frac{n(n+1)}{2}$ . ### T2 一棵有根树，多次操作，给一颗子树中的节点增加权值。 板。 ### T3 ......
P7819 [RC-05] Xor Matrix
~~被这题恶心死了~~ 对于矩阵比较小的可以暴力做。 容易发现这个 $k$ 进制下异或和是可以容斥的。 枚举答案的位数 $p$，即求： $$\sum_{i=1}^{x}\sum_{j=1}^{y}\lfloor\frac{(i-1)m+y}{k^p}\rfloor\mod k$$ 然后利用类欧可以得 ......
多项式
先放一个 $\rm NTT$ 的板子。 ```cpp #include #define N 1>=1; } return ret; } int f[N],g[N],h[N]; int n,lim=1,r[N]; int gn,tp,inv; void ntt(int *x,int lim,int o ......
Kruskal 重构树
$\text{Kruskal}$ 重构树基于 $\text{Kruskal}$ 最小生成树算法，通过将边权化为点权实现一些奇妙东西。 ### 构造 与 $\text{Kruskal}$ 最小生成树算法类似。 当连边 $(u,v,w)$ 时： - 新建节点 $x$，将其点权设为 $w$. - 设 $u ......
动态 DP
[P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 带点权的树，每次修改一个点的权值，求树的最大权独立集。 $1\le n,m \le 10^5$，点权的绝对值 $\le 10^2$. 若不带修，先设 $f_{u,1/0 ......
2023.5.18
### T1 已知 $a,b$ 为互素的正整数，求最大的 $k$， $$ax+by=k$$ 无非负整数解。 [P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目](https://www.luogu.com.cn/problem/P3951) 小丑，答案 ......
2023.5.19
### T1 已知 $\gcd(a,b)=G,\text{lcm}(a,b)=L$，求 $\min\{a+b\}$，无解 $-1$. $1\le T\le 5$，$1\le G,L\le 10^{12}$. 无解即当 $G\not|\space L$. 有 $$\frac{a}{G}\cdot\fr ......
生成函数
[P4451 [国家集训队]整数的lqp拆分](https://www.luogu.com.cn/problem/P4451) 求 $$\sum_{\sum_{i=1}^{m}a_i=n,a_i>0}\prod_{i=1}^{m}f_{a_i}$$ $f$ 是斐波那契数列，$f_0=0$，$f_1= ......
笛卡尔树
[高思诚](https://www.luogu.com.cn/user/253936)是后门中学的学生。 $\text{On 2023.5.31}$.  记 $f(x)$ 为数字串 $x$ 中数码众数的出现次数。 求 $\sum_{i=l}^{r}f(i)$. $1\le T\le 10^3$，$1\le l,r\l ......
2023.7.3
### A 求把一张无向图的所有边变为有向边，使得各点出度为 $1$ 的方案数。 答案对 $998244353$ 取模。 $1\le n,m\le 2\times 10^5$. 首先一定有 $n=m$，然后环上的边有两种取法。 把环数找出来，然后判断这个连通块中 $E$ 是否等于 $2V$. ``` ......
第二类斯特林数
第二类斯特林数 $\begin{Bmatrix}n\\k\end{Bmatrix}$，意义为将 $n$ 个不用的元素分为 $k$ 个非空子集的方案数。 有 $\displaystyle\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\e ......
2023.7.5
### A 排队打水，$n$ 个人，$m$ 个水龙头，最小化总时间。 显然是一个 trival 的贪心。 ```cpp #include #define N 1010 #define pii pair #define mp make_pair #define fi first #define se ......
Prufer 序列
#### Tree $\rightarrow$ Prufer - 每次找到编号最小的叶子结点，在序列中添加其父亲。 - 删除该节点。 - 重复如上操作，得到长为 $n-2$ 的序列。 还原同理。 Prufer 序列是 $n$ 个点的完全图的生成树与一个长为 $n-2$，值域 $\lbrack 1,n ......
模拟退火
模拟退火（Simulate Anneal）是一种用于解决问题方案数极大且非单峰函数的随机化算法，原理与金属退火类似。 每次随机出一个新解，若新解更优则接受，否则以一个与温度和与最优解的差相关的概率接受它。 ### 降温 模拟退火有三个参数：初始温度 $T_0$，降温系数 $\Delta$，终止温度 ......
后缀数组
## SA ### 基数排序 一般采用 LSD(Least Significant Digital)，从键值的最低位开始排序。 ### 定义 记 $suf(i)$ 为起始下标为 $i$ 的后缀。 记 $sa[i]$ 为排名第 $i$ 的后缀的起始位置。 记 $rk[i]$ 为 $suf(i)$ 的排 ......
后缀自动机
### 定义 字符串 $s$ 的 SAM 是一个接受 $s$ 的所有后缀的最小 DFA（确定性有限（状态）自动机）。也就是： - SAM 是一个 DAG。节点为状态，边为转移。 - 图的源点 $t_0$ 称初始状态。整张图从 $t_0$ 开始可以遍历到。 - 转移标有若干字母，从一个节点出发的所有转 ......
群相关
### 群 **群**是由一个集合及一个二元运算组成的代数结构，记为 $(G,\cdot)$. 其符合**群公理**，即满足**封闭性，结合律，单位元，逆元**。 ### 子群 群 $(G,\cdot),(H,\cdot)$，满足 $H\subseteq G$，则 $(H,\cdot)$ 是 $(G ......
一些 trick
#### 高次整除分块 对 $\large\lfloor\frac{n}{i^2}\rfloor$ 整除分块，$\large r=\sqrt{\lfloor\frac{n}{\lfloor\frac{n}{l^2}\rfloor}\rfloor}$. 容易发现对于 $i\le n^{\frac{1} ......
2023.8.3
#### A 01 矩阵，每次可以对一个子矩阵取反，问最少多少次操作后，存在一条只向下或右走，只经过 0，从左上角到右下角的路径。 $n,m\le 1000$. 这个 dp 还是非常 trival 的。 ```cpp #include #define N 1010 #define inf (11?f ......
字符串相关
### KMP 下标从 $1$ 开始求 border： ```cpp int kmp[N]; void KMP(char *s,int len){ for(int i=2,j=0;ir)l=i,r=i+z[i]-1; } } ``` [P5410 【模板】扩展 KMP（Z 函数）](https:// ......