洛谷4156 [WC2016]论战捆竹竿
Luogu UOJ 分析 求出 $s$ 的所有周期 $l_1, l_2, \cdots, l_k$，那么我们相当于要求有多少个 $x \in [0, w - n]$ 满足存在一组 $\{x_i \geq 0\}$ 使得 $\sum_{i = 1}^k x_i l_i = x$。 发现如果 $x$ 可以，那么 $x + n$ 也一定可以，于是我们可以在模 $n$ 意义下跑同余类最短路（这里最短...
Luogu UOJ 分析 求出 $s$ 的所有周期 $l_1, l_2, \cdots, l_k$，那么我们相当于要求有多少个 $x \in [0, w - n]$ 满足存在一组 $\{x_i \geq 0\}$ 使得 $\sum_{i = 1}^k x_i l_i = x$。 发现如果 $x$ 可以，那么 $x + n$ 也一定可以，于是我们可以在模 $n$ 意义下跑同余类最短路（这里最短...
AtCoder 分析 设 $T$ 为 $S$ 减去 $S$ 的最长 border 后缀后得到的串。 如果 $|T|$ 是 $|S|$ 的约数，那么操作得到的串依次是 可以发现，$s_i=s_{i-1}+s_{i-2}$。 那么串长增长的速度是指数级别的，所以我们可以直接暴力地算出前若干个这样的串中每个字符的个数，询问时把 $[1,r]$ 拆成若干个这样的串相接再加上不是一个完整的 $S$ ...
Luogu 分析 容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。 第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到 第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$...
Luogu 分析 以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。 设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。 分析一下可以列出这样一个式子 用 KMP / has...