UOJ Round #6
A. 破解密码
20
$n \le 5$
暴搜。
时间复杂度 $\mathcal O(26^n n)$。
50
$n \le 100$
高斯消元。
时间复杂度 $\mathcal O(n^3)$。
100
$n \le 10^5$
设 $a_i$ 首字母为 $c$。
\[\begin{aligned} & h_{i + 1} \\ = & ((h_i - 26^{n - 1} \times \text{num}(c)) \times 26 + \text{num}(c)) \bmod p \\ = & (26 \times h_i - 26^n \times \text{num}(c) + \text{num}(c)) \bmod p \end{aligned}\]对于每个 $i$ 枚举 $c$ 验证是否合法即可。
注意当 $26^n = 1$ 时，$h_{i + 1} = 26 \times h_i \bmod p$，此时任意 $c$ 都是合法的。
只有当 $f(s) = h_0$ 时 $s$ 才是合法的答案，那么根据 $h_0$ 生成一个 $s$ 即可。
B. 智商锁
20
$k \le 100$ 且 $k \le 2$
$n$ 个点的环的生成树个数恰好为 $n$。
特判 $k = 0$ 的情况。
40
保证存在 $n \le 6$ 的图满足题意
$6$ 个点的标号无向图只有 $2^{\binom{6}{2}} = 2^{15}$ 个，暴搜出每一张图，用矩阵树定理计算其生成树个数。
60
$k = 3, 16, 125, 1296, 16807, 262144, 4782969, 229805564, 305655011, 988403481, 987167444, 826614133$
$n$ 个点的完全图生成树个数为 $n^{n - 2}$
70
$k = 110, 221, 667, 1457, 2021$
将 $k$ 分解质因数，用割边将若干 $k$ 很小的图连通起来。
根据乘法原理，连通后的图生成树个数为小图生成树个数之积。
100
$k \lt 998244353$
随机 1000 张点数为 12 的无向图，用矩阵树定理求出第 $i$ 张图的生成树个数 $f_i$。
对于每一个 $k$，我们试图找到一个四元组 $(a, b, c, d)$ 使得 $f_a \times f_b \times f_c \times f_d \equiv k \pmod 998244353$，这个显然可以 meet in middle。
C. 懒癌
10
每户人家都能看出其他每户人家的狗有没有得懒癌
如果有 $k$ 只生病的狗，一定会在第 $k$ 天传来第一次的枪声。
而且因为这 $k$ 个狗主人的状况是完全等价的，所以他们一定会同时开枪。
一个有 $k$ 只生病的狗的生病状况，对总开枪时间和总枪声数的贡献都是 $k$。
两问的答案都是 $\sum_{i = 1}^n \binom{n}{i} \times i$。