题目大意

给定一个长度不超过 $14$ 的字符串，以及素数 $m$ 和正整数 $p (p > 1)$。要求构造一个长度不超过 $14$ 的字符串，它不等于原字符串，并且以 $p$ 为进制，$m$ 为模数的哈希值等于原串的哈希值。

字符集大小为 $63$，$m \le 10^{12}, p \le 2000, p^{13} > m$。

题目大意

「BZOJ 4318」OSU!

有一个长度为 $n$ 的 $01$ 串，第 $i$ 位有 $p_i$ 的概率为 $1$，有 $1 - p_i$ 的概率为 $0$。每一段长度为 $x$ 的极长的 $1$ 对得分有 $x^3$ 的贡献。问期望得分。

数据范围：$n \le 10^5$。

题目大意

定义一个字符串的熵为：

其中 $p_{c}$ 为字符 $c$ 在字符串中的占比。例如 aaabb 中 $p_a = 0.6$。

给定实数 $x$，要求构造一个长度不超过 $10^3$，字符集大小不超过 $64$ 的字符串，它的熵 $y$ 满足 $\vert x - y \vert \le 5 \times 10 ^ {-3}$。

数据范围：$0 \le x \le 6$。

题目大意

「Codeforces 528D」Fuzzy Search

给定两个字符串 $S, T$（只包含 $4$ 个字母）和非负整数 $k$，定义模式串和文本串的一段是模糊匹配的，当且仅当对于模式串中的每个位置 $i$，都能在文本串中找到字符 $S_j = T_i$ 且 $\vert i - j \vert \le k$。

问模式串被匹配了几次。

我们记 $n = \vert S \vert, m = \vert T \vert$。

数据范围：$n, m, k \le 2 \times 10^5$。

题目大意

「Codeforces 1096G」Lucky Tickets

给定偶数 $n$ 和 $k$ 个数位，求长度为 $n$ 的数字串，满足只使用给定的数位，且前 $\frac{n}{2}$ 位的和等于后 $\frac{n}{2}$ 位的和的个数 $\bmod 998244353$ 的结果。

数据范围：$n \le 2 \times 10^5$。

题目大意

「AHOI / HNOI 2017」礼物（Luogu 3723）

有两个长度为 $n$ 的手环，每个位置上的亮度分别为 $x_1, x_2, \cdots, x_n$ 和 $y_1, y_2, \cdots, y_n$，它们都是 $[1, m]$ 中的整数。你可以给某个手环整体加上 $c$（整数），并将它旋转（循环位移）$k$ 位，然后使得 $\sum_{i = 1}^{n} (x_i - y_i) ^ 2$ 最小。

数据范围：$n \le 5 \times 10^4, 1 \le m \le 100$。

快速傅立叶变换（Fast Fourier Transformation）可以将多项式在系数表示法和（单位复根的）点值表示法之间互相转化，而它的时间复杂度仅为 $O(n \log n)$。

推荐阅读

Algocode 算法博客

题目大意

「Codeforces 19E」Fairy

给定一个 $n$ 个结点 $m$ 条边的无向联通图，问删去那些边后图是二分图。

$n, m \le 10^4$。

题目大意

「SDOI 2018」战略游戏（Luogu 4606）

给定 $n$ 个点 $m$ 条边的无向图，$q$ 次询问，每次询问点集 $S$，求图中有多少个点满足删掉它之后 $S$ 中至少两个点不联通。

$n, q \le 10^5, m, \sum \vert S \vert \le 2 \times 10^5$。

题目大意

「BZOJ 1718」Redundant Paths

给定一个 $n$ 个点 $m$ 条边的无向图，问至少再加几条边就能使得整个图形成一个边双联通分量。

边双联通分量的定义：一个图中的任意两个结点之间都有两条路径，满足它们的边没有交。

数据范围：$n, m \le 10^6$。