UOJ Round #1
A. 缩进优化
20
$n \le 10^3$
$a_i \le 2000$
枚举 $x$，答案为 $\sum_{i = 1}^n \lfloor \frac{a_i}{x} \rfloor + (a_i \bmod x)$。
$x$ 的上界为 $a_i$，时间复杂度 $\mathcal O(na)$。
40
$n \le 10^5$
$a_i \le 2000$
$n$ 的规模远大于 $a_i$，同一个 $a_i$ 会出现多次。
$a_i$ 的顺序与答案无关，同一个 $a_i$ 对答案贡献相同。
于是可以统计 $a_i$ 的数量，对于同一个 $a_i$ 只考虑一次，避免重复枚举。
时间复杂度 $\mathcal O(n + a^2)$。
70
$n \le 10^5$
$a_i \le 10^5$
换个角度思考问题。
每次将长度为 $x$ 的 空格 替换为 TAB，总长度减少 $x - 1$。
记 $b_x = \sum_{i = 1}^n \lfloor \frac{a_i}{x} \rfloor$，即每行可替换次数，答案为 $\sum_{i = 1}^n a_i - b_x \times (x - 1)$。
这是一个整除分块的形式，对于一个 $a_i$，$\lfloor \frac{a_i}{x} \rfloor$ 最多有 $\sqrt a$ 种取值。
对于一个 $a_i$，枚举使得 $\lfloor \frac{a_i}{x} \rfloor$ 相同的 $x$ 的区间 $[l, r]$，将 $\lfloor \frac{a_i}{x} \rfloor$ 累加到 $b_x$，对 $b$ 数组使用前缀和与差分以做到 $\mathcal O(1)$。
最后枚举 $x$ 计算答案。
时间复杂度 $\mathcal O(n + a \sqrt a)$。
记得对 $b$ 数组开 long long。
100
$n \le 10^6$
$a_i \le 10^6$
把问题想复杂了。
换个角度思考问题。
考虑直接计算 $b_x$。
对于一个 $x$，枚举 $t = \lfloor \frac{a_i}{x} \rfloor$，则符合要求的 $a_i$ 属于 $[t \times x, (t + 1) \times x)$，将 $\sum_{a_i = t \times x}^{(t + 1) \times x - 1} c_{a_i} \times t$ 累加到 $b_x$，对 $c$ 数组使用前缀和与差分以做到 $\mathcal O(1)$。
$t$ 的上界为 $\frac{a_i}{x}$，根据调和级数 $\sum_{i = 1}^n \frac{1}{i} = \log n$，时间复杂度 $\mathcal O(n + a \log a)$。
注意避免访问溢出。
B. 外星人
40
- 当 $x \lt a_i$ 时，$x \bmod a_i = x$。
- 当 $x \ge a_i$ 时，$x \bmod a_i \lt a_i$。
若使用 $a_i$ 则必有 $x \bmod a_i \lt a_i$。
若有 $a_i \lt a_j$，则使用 $a_i$ 后 $a_j$ 对 $x$ 无影响。
将 $a_i$ 从大到小排序依次考虑。
记 $f_{i, j}$ 表示考虑前 $i$ 个外星人，当前 $x$ 为 $j$ 的状态。
\[f_{i, j \bmod a_{i}} |= f_{i - 1, j}\]时间复杂度 $\mathcal O(nx)$。
注意答案的范围在 $[0, \min a_i)$。
46
$n \le 10$
$x, a_i \le 20$
枚举全排列，统计方案数。
时间复杂度 $\mathcal O(n \times n!)$。
58
$n \le 50$
$x, a_i \le 100$
记 $f_{i, j, k}$ 表示考虑前 $i$ 个外星人，当前 $x$ 为 $j$，还剩 $k$ 个外星人的手指数比 $j$ 大的状态。
第 $i$ 个位置有两种选择：
- 放有效的外星人
- 放无效的外星人
由于当前 $x$ 为 $j$，说明手指数 $\le j$ 的外星人都没有用过。
所以我们可以从 $k$ 个剩下的外星人或者手指数 $\le j$ 的外星人中选一个进行转移。
时间复杂度 $\mathcal O(n^3 x)$。
76
$n \le 100$
$x, a_i \le 500$
$i$ 是打酱油的。
时间复杂度 $\mathcal O(n^2 x)$。
100
$n \le 1000$
$x, a_i \le 5000$
$k$ 是打酱油的。
时间复杂度 $\mathcal O(n x)$。
记 $f_j$ 表示当前 $x$ 为 $j$ 且只考虑手指数 $\le j$ 的外星人的状态。
考虑手指数属于 $[1, j]$ 的外星人 $k$，显然一定是有效外星人。
考虑手指数属于 $(j \bmod a_k, j]$ 的外星人，把他们随便插入到 $f_{j \bmod a_k}$ 的最优解排列中去就可以了。
这个显然可以用简单的组合数学解决，方案数即 $\frac{(c_j - 1)!}{c_{j \bmod a_k}!}$。其中 $c_j$ 表示手指数不超过 $j$ 的外星人个数。
C. 跳蚤国王下江南
20
$n \le 14$
暴力 DFS 出所有路径。
50
$n \le 1000$
在圆方树上树形 DP。
如果遇到方点，则枚举方点的儿子，边权为环上顺逆时针两种走法的长度。
时间复杂度 $\mathcal O(n^2)$。
70
保证对于 $1 \le i \lt n$，$i$ 与 $i + 1$ 之间存在至少一条道路直接相连
仙人掌的主体是一条链，在链上有一些反祖边，且返祖边对应链上的区间不相交。
把环当作一个整体，这样就可以把原图看作一个边和环组成的序列。
考虑生成函数，对于一个链式仙人掌，定义多项式 $f(x)$ 与 $g(x)$，其中 $[x^k] f(x)$ 代表从链式仙人掌的起点开始走，长度为 $k$ 的简单路径数量，$[x^k] g(x)$ 代表从链式仙人掌的起点开始走，走到链式仙人掌的终点（链的另一头），长度为 $k$ 的路径数量。
们每次把序列劈成两半，求出左边的信息和右边的信息，然后拿左边的 $g(x)$ 乘以右边的 $f(x)$，再加上左边的 $f(x)$ 就得到了总体的 $f(x)$，至于总体的 $g(x)$，把左边和右边的 $g(x)$ 乘起来就行。
如果序列分得不能再分，说明只剩了一条边或者一个环，这个显然可以轻松求出 $f(x)$ 和 $g(x)$。
使用 FFT 进行多项式乘法，时间复杂度 $\mathcal O(n \log^2 n)$。