写在前面

发现自己菜爆了，总共做出三个来，还有个网络流不会写的，疯狂看不懂题目，字符串一点不会。。

A

阅读理解题，判断一个序列是否所有数都满足能够被 $3$ 整除。

B

没看，看样子大概率不会填了。

C

给定一个序列，求一个子序列使得其逆序对数与序列长度的比值最大。

最大密度子图，二分答案转化为最大权闭合子图来求即可。

D

没看，大概率不填。

E

同(就算没看也要把这题序号写在这里.jpg)。

F

假设你有 $n$ 朵鲜花，你要涂色，你一共有 $m$ 种颜色可以涂，但是你要保证涂完后所有的鲜花恰好有 $k$ 种颜色。

二项式反演，我们你有 $m$ 种颜色且恰好都用上的方案数为 $f(m)$，有

$$ \sum_{i = 0}^mC_{m}^if(i) = m(m - 1)^{k - 1} $$

我们设 $g(m) = m(m - 1)^{k - 1}$，利用二项式反演，可以得到：

$$ f(m) = \sum_{i = 0}^m(-1)^{m - i}C_{m}^ig(i) $$

最终答案就是 $C_{n}^kf(k)$。

G

回文自动机还是回文树好像，一点都不会字符串，这个放了。

H

没看，鸽。

I

看不懂题目，鸽。

J

鸽。

H

有点意思的题目。

给定一个数列 $S_n$ 满足如下：

$$ S_0 = A $$

$$ S_1 = B $$

$$ S_n = |S_{n - 1} - S_{n - 2}| \quad \forall n > 1$$

问你 $S$ 中不同的数的数量。

看起来很像求 $\gcd$ 的那个东西，试着用这个做一下。

我们假设 $g(a,b)$ 是 $S_0 = a, S_1 = b$ 时的答案。

Part 1

我们先考虑 $a > b$ 的情况。

我们可以发现在这里 $a$ 不断在减 $b$ 知道小于 $b$ 为止。

比如 $16,3$开头的序列是一个这样的情况：

$$ 16,3,13,10,3,7,4,3,1,\dots $$

我们可以看到 $16,13,10,7,4$ 就是从 $16$ 开始不断减 $3$。

那么我们可以一次性把这些数全部统计进去，大于 $b$ 的数一共 $\lfloor \frac ab\rfloor$ 种。

然后加上 $g(3,1)$ 就好了。

也就是 $g(b, a \mod b)$。

注意这里 $b$ 可能在后边，变成 $g(a \mod b, b)$。

主要是看 $\lfloor \frac ab\rfloor$ 奇偶性，奇数在前偶数在后。

需要特判 $a \mod b = 0$ 的时候，这个时候答案就直接是 $\frac ab + 1$。

Part 2

那么我们接下来考虑 $a = b$ 的情况，这里直接返回 $2$ 就好了。

Part 3

接下来就是 $a < b$ 的情况，我们举一个具体例子来看下。

$$ 2, 5, 3, 2 $$

发现这个时候我们只要求 $g(5,3)$ 就好了，即 $g(b, b - a)$。

最后别忘了特判 $g(0,0) = 1$，很容易漏。