好久没更了 = =

现在看到什么题都感觉一脸不可做，水平太低了

题意

给出仅包含小写字母的长度为 $n$ 的字符串 $s$

每次取出 $s$ 的一个子串 $t_i$（可以为空），执行 $m$ 次，顺次拼接成一个大字符串 $t=t_1 t_2\dots t_m$，求可以得到多少种本质不同的 $t$

$q$ 次询问，每次给出一个 $m$

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

BZOJ 1921

题意

给一棵 $n$ 个点的树和长度为 $m$ 的特征串，树的每个节点有一个字符。

求随机两个点形成有向路径上构成的串在特征串里出现次数的期望

仅含小写字母，$n,m\le 5*10^4$

第一篇算法相关

第一次自己想sam

Codeforces 1063F

题意

给出一个长度为$n$的字符串$s$。

如果一个字符串序列$t_1,\dotsc,t_k$，$\forall1<i\le k$，$t_i$是$t_{i-1}$的一个子串，且长度严格小，那么称这个字符串序列是一个journey。

一个journey的长度是其中字符串的数量

求最长的journey，满足存在字符串序列$u_1,\dotsc,u_{k+1}$(可以为空)，使$s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}$。