hk_cnyali's Blog

给定 $n$ 个字符集为小写字母的字符串 $s_i$

一个串 $t$ 是可接受的，当且仅当 $t$ 可以表示成 $p_1 + p_2 + \cdots + p_n$，其中 $p_i$为 $s_i$的一个子串（可以为空），$+$ 表示字符串的拼接

问有多少种本质不同的字符串 $t$ 是可接受的

答案对 $10^ 9 + 7$取模

几次尝试学这个都没太搞懂，过几天就忘

今天看了一个讲得超级好的课件之后才真正理解SAM

趁热写一点笔记，省得以后又全忘了

可能大部分都是从ppt里搬来的吧。。。

感觉这一场的后面两题稍微比18DEC的要难一点点

T2的一些小细节想了很久，问了jambow；T3最后一点边界情况没想清楚，经dis提示后才会

最近屈哥布置的USACO的月赛题，难度不是太大，但是T2的一些小细节还是没太想清楚，看了下题解

给你一棵$n$个节点的模板树，一棵大树初始等于模板树

给出$m$次操作，每次把模板树中以$x$为根的子树复制，并接到大树的$y$号节点上

然后对新节点重标号，新节点的编号为大树在上一次操作结束时的节点数加上这个节点在模板树那棵子树里的排名

有$q$次询问，每次询问大树上两个节点的距离

$n, m, q\le 10^5$

给你一棵$n$个节点的树，有$m$次操作，操作包含以下三种：

1. 新建一个从$u$到$v$的任务，权值为$w$
2. 删除第$i$个任务
3. 询问所有不经过的任务中最大的权值

$n\le 10^5, m\le 2*10^5$

给定一张 $N$ 个顶点 $M$ 条边的带边权无向图，所有权值都可以分解成 $2^a \cdot 3^b$的形式

现在有 $q$ 个询问，每次询问给定四个参数 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a \cdot 3^b$

注意：路径可以不是简单路径。

$n,q\le 5*10^4, m\le 10^5$

给你一张$n$个点$m$条边的图，每次会随机选择一个还未删除的点 $v$，然后访问所有与 $v$ 连通的点，然后删除点 $v$ ，直至所有点都被删除。

求期望访问次数，答案对$998244353$取模

$n\le 10^5, m\in[n - 1, n]$

发现以前没写过模拟退火相关的东西，就在这里提一下吧

给出一个$n$个点，$m$ 条边的无向图，求由 $k$ 条边构成的联通子图的个数，对$10^9 + 7$取模

$n\le10^5,m\le2*10^5,k\le4$