题解
后缀自动机（SAM）
题意
求字符串字典序第 $k$ 大子串（本质不同或位置不同）。
$n\leq 5\times 10^5$
题解
DP 求得结点大小（size），再 DP 求 DAG 子树（或子图？）的大小，像平衡树那样转移即可。
代码
const int N = 1e6 + 10;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
wh …
Jayun 发布于 2023-04-24 17:11:49
11
后缀自动机（SAM）基础线段树
题意
给定一个长为 $n$ 的字符串 $s$ 和 $m$ 个问题，每个问题均有 $a,b,c,d$ 四个参数，求子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。
$1\le n,m\le 100,000$ 。
题解
SAM 例题。直接算长度太难，考虑二分长度：若二分到长度为 $\mathrm{len}$ ，接着查询子串 …
Jayun 发布于 2023-04-24 11:53:49
00
数学推导杂项
题目描述
一个 $n\times m$ 数独是一张包含 $m\times n$ 个区域的网格，其中每个区域包含 $n\times m$ 个格子，因此一个 $n\times m$ 数独共有 $nm\times nm$ 个格子。 $n\times m$ 数独的每行、每列、每个区域都恰好包含 $[1,nm]$ 的所有整数。
对于某行或某列，从某个方向开始，依次列出这行（列）的 …
Jayun 发布于 2023-03-27 18:25:59
00
快速数论变换（NTT）斯特林数计数组合意义快速傅里叶变换（FFT）
题意
定义一个无向图的权值为所有结点度数的 $k$ 次方之和（规定 $0^0=1$ ）。
求所有 $n$ 个点的简单无向图的权值之和。
答案对 998244353 取模。
$n\leq10^9,0\leq k\leq5\times10^5$ 。
题解
可以对于每个点的贡献然后乘 $n$ 。考虑每个点贡献的组合意义，相当于是 $k$ 个有标号点放进 $d$ 个有标号桶里，并且可 …
Jayun 发布于 2023-01-28 07:53:08
00
重链剖分（HLD）
题意
给定一棵 $n$ 个点的有根树，其中 $1$ 号点是根，定义 $f(x)=\sum_{i\leq j,\mathrm{LCA}(i,j)=x}(w_i+w_j)$ 。
现在你需要支持两种操作：
1 x v：对于所有 $x$ 子树内和 $x$ 距离不超过 $2$ 的点 $y$ ，令 $w_y\leftarrow w_y+v$ 。
2 x：询问 $f(x)$ 的值。 …
Jayun 发布于 2023-01-28 07:52:57
00
费用流SPFA
题意
一个长度为 $n$ 的整数序列 $\{h_i\}$ ， $m$ 种操作，每种操作为花费一定的代价将一段长度为给定值的连续子区间加一或减一，每种操作都可以使用任意多次。
求把 $\{h_i\}$ 变成单调不降的最小代价，或者判断无解。
$n,m\leq200$ 。
思路
区间加一减一，用差分维护，设差分数组 $a_i=h_i-h_{i-1}$ 。那么目标就是要使所有 $a_i …
Jayun 发布于 2023-01-28 07:52:51
00
构造计数
大意
给定长度为 $n$ 的系数数组 $a_i$ 和 $l,r$ ，求出长度为 $n$ 的数组 $x_i(x_i\in\mathbb{N})$ 使得：
$$l\leq \sum_{i=1}^na_ix_i\leq r
$$
问 $x_i$ 数组有多少个。
$n\leq 12,1\leq l\leq r\leq 9\times10^{11},1\leq a_i\leq5\ti …
Jayun 发布于 2022-11-25 16:58:52
00
KMP 算法计数矩阵快速幂
题目
阿申准备报名参加 GT 考试，准考证号为 $N$ 位数 $X_1,X_2,…,X_n$ ，他不希望准考证号上出现不吉利的数字。
他的不吉利数字 $A_1,A_2…A_m$ 有 $M$ 位，不出现是指 $X_1,X_2,…,X_n$ 中没有恰好一段等于 $A_1,A_2,…,A_m$ ， $A_1$ 和 $X_1$ 可以为 $0$ 。阿申想知道不出现不吉利数字的号码有 …
Jayun 发布于 2022-11-21 17:17:04
00
基础线段树
题目
给出一个长度为 $n$ 的 $k$ 进制数，可能含有前导 $0$，你需要实现以下 $4$ 种操作，共 $m$ 次。
1 x y：将第 $x$ 位上的数改为 $y$；
2 l r：将第 $l$ 位到第 $r$ 位升序排列；
3 l r：将第 $l$ 位到第 $r$ 位降序排列；
4 l r：求第 $l$ 位到第 $r$ 位所组成的 $k$ 进制数转为 $10$ 进制数的结果，结果对 $998 …
Jayun 发布于 2022-10-18 16:11:14
00
斜率优化动态规划（斜率优化 DP）
题目
城市中有一条长度为 $n$ 的道路，每隔 $1$ 的长度有一个公交车站，车站的编号从 $0$ 到 $n$，市政府在 $0$ 号车站的位置。
城市中同时有 $n$ 趟公交线路，第 $i$ 条公交线路的起点站为 $i-1$。公交车站 $i(0\leq i\leq n)$ 有两个属性 $c_i$ 和 $v_i$，代表从这个公交车站出发的公交车的性质。
$c_i$ 代表这个从 $i$ 出发的公交车， …
Jayun 发布于 2022-10-17 21:14:51
00