分类

$\color{Green}{Easy}$：一眼题。

$\color{Blue}{Median}$：经过思考可以做出来。

$\color{Yellow}{Hard}$：看完题解立马理解。

$\color{Orange}{Insane}$：看完题解经过一段时间的思考能够理解。

$\color{Red}{Supreme}$：看完题解经过长久思考才理解。

洛谷-P3327 约数个数和 $\color{Blue}{Median}$

掏出经典结论：$ d(i, j) = \sum_{x | i} \sum_{y | j} [\gcd(i, j) = 1] $，然后就基本上做完了。

最后得到的式子为：

$$\sum_{i = 1}^n \mu(i) \sum_{x = 1}^{\lfloor \frac{n}{x} \rfloor} \lfloor \frac{n}{i x} \rfloor \sum_{y = 1}^{\lfloor \frac{m}{y} \rfloor} \lfloor \frac{m}{i y} \rfloor $$

洛谷-P3704 数字表格 $\color{Green}{Easy}$

也是套路了，最后可以推出答案为：

$$\prod_{i = 1}^n g(i)^{\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor} $$

其中 $g(x) = \prod_{d \mid x} f(d)^{\mu{\frac{x}{d}}}$

而 $g(i)$ 是可以 $O(n \log n)$ 预处理出来的，然后就做完了

BZOJ-4174 tty的求助 $\color{Green}{Easy}$

取个 mod 就可以了。

BZOJ-3601 一个人的数论 $\color{Orange}{Insane}$

wc 居然是用拉格朗日插值优化，畏惧了。

LibreOJ-6077 逆序对 $\color{Blue}{Median}$

容斥 + dp 即可。

CSES-2421 Counting Reorders $\color{Green}{Easy}$

也是容斥 + dp。

P3813 [FJOI2017] 矩阵填数 $\color{Green}{Easy}$

离散化容斥即可，时间复杂度 $O(n^3 2^n)$。

黑暗爆炸-2863 愤怒的元首 $\color{Blue}{Median}$

考虑一个个去掉出度为 $0$ 的点，则可以得出状态转移方程：

$$dp_i = \sum_{j = 1}^{i} dp_{i - j} 2^{j (n - j)} \binom{i}{j} (-1)^{j + 1} $$

时间复杂度 $O(n^2)$。

洛谷-P3349 小星星 $\color{Yellow}{Hard}$

看错题了（不嘻嘻）。

使用状压 dp + 子集反演即可，要卡常。

LibreOJ-6185 烷基计数 $\color{Green}{Easy}$

注意到一个奇怪的条件：度数 $\leq 4$。

直接暴力 dp 就可以了。

CodeForces-722E Research Rover $\color{Green}{Easy}$

还是简单 dp + 容斥。

CodeForces-1228E Another Filling the Grid $\color{Green}{Easy}$

建议降黄，小学生会做。

CodeForces-1342E Placing Rooks $\color{Yellow}{Hard}$

这题有一个关键性质：每一行/列都有车。

然后就可以直接上容斥了。

POJ-3904 Sky Code $\color{Green}{Easy}$

莫比乌斯反演即可。

CodeForces-1400G Mercenaries $\color{Green}{Easy}$

简单容斥，建议降绿。

HDU-3908 Triple $\color{Yellow}{Hard}$

omg 满级思维题。

将求 0 对和 3 对 转换为求 1 对和 2 对，然后就可以乱搞了。

时间复杂度 $O(T n^2 \log V)$。

AtCoder-arc096_c Everything on It $\color{Yellow}{Hard}$

首先还是容斥，考虑有 $j$ 个数出现次数 $\leq 1$，但是有的配料可能压根没有出现，就很难计算。

然后我认为最神的一步来了，加入一个配料 $0$，如果一个配料与 $0$ 分在一组，则可以认为压根没用这个配料。

然后就是简单题了。