高考后复健日记

2024.6.16

挑了套简单 ABC 找找状态，做了 E、F、G。

E 稍微思考一下会发现有用的量是每种字母选的个数，记第 $i$ 种字母用了 $a_i$ 个，那么答案就是 $\binom{n}{a_1}\binom{n - a_1}{a_2}\binom{n - a_1 - a_2}{a_3}...\binom{n - a_1 - a_2 - ... - a_{n - 1}}{a_n}$。

化简一下就是 $\dfrac{n!}{\prod{a_i!}}$，发现只需要预处理阶乘和其逆元，然后设 $f_{i}$ 表示当前长度为 $i$ 的字符串的数量，即可快速转移。

F 一开始想，怎么让每种可能长度的路径，都能按一种形式化的流程表示出来，画了若干图之后，发现可以一直贴左边和上边走，直到当前情况下可以用最短路直达，然后就走最短路。

实现花了一点时间，不过也还好。

G 观察了一下性质发现，存在至少一种最优方案，是一开始乱走，然后留在一个点不动的。

然后大脑宕机了，顺着 F 思考，想着怎么强制要求其不走重复点，感觉似乎不太容易。看了一下讨论区发现其实走重复点也没什么问题，于是问题可以用 dp 轻松解决。