Educational Round 165
C. Minimizing the Sum
这是一道区间dp题。 $f_{i,j}$ 表示到第 $i$ 个下标为止使用 $j$ 次操作所能获得的最小的前缀和，不考虑 $i$ 右侧的数。
由于总的操作次数很有限 $(k\leq10)$，我们可以考虑对后 $t$ 个数全部操作，也就是把 $a_{i-t},…,a_i$ 全部变为他们之中的最小值。然后答案由 $f_{i - t - 1,j - t}$ 转移过来。
状态转移的瓶颈在区间最小值，可以动态地维护，也可以使用ST表。
Submission #301206954 - Codeforces
D. Shop Game
Bob显然是白嫖最贵的 $k$ 件物品。我们考虑Alice，假设Alice选了 $m(m\geq k)$ 件物品，那么我们希望 $m-k$ 的那些物品都是赚钱的，而被白嫖的 $k$ 件物品尽量损失少。如果实在赚不到钱，一件也不选，最小答案应该是 $0$。现在，我们把物品根据Bob的价格 $b_i$ 由小到大排序，枚举分段点，这时分段点右侧的 $b_i$ 永远大于左侧，因此把右侧看作让Bob白嫖k件的，左侧看作赚钱的。从右往左遍历分段点，使用大根堆维护右侧的k件物品，如果新的物品比最大值要小，那么就替换掉堆顶的元素（我们希望损失尽量小）。在分段点左侧，我们预先处理好能赚钱的部分的前缀和，那么可以 $O(1)$ 求出利润。
Submission #301235628 - Codeforces
Round 894 (Div. 3)
F. Magic Will Save the World
这是我补充的一道dp题，但是一开始也没看出要咋dp。
首先，所有的施法不需要时间，可以到最后把怪物一起消灭。如果我们能够确定使用火魔法的怪物总血量 $X$，那么就可以在 $O(1)$ 求出答案。
现在问题转化为：有一堆数，取出一些加起来，总共能得到哪些数。
这个问题可以转化为01背包。把每个数 $y$ 看成一件价值为 $y$，体积为 $y$ 的物品。我们用 $f_i$ 表示填满一个容量为 $i$ 的背包所能获得的最大价值，经过01背包dp过后，所有 $f_i$ 的值组成的集合就是我们能够组合出的 $X$ 。
Luogu
P5431 【模板】模意义下的乘法逆元 2
线性求 $1$ 到 $n$ 的逆元，线性求 $n$ 个数的逆元，以及处理阶乘的逆元其实本质都差不多。
对这道题，我们考虑 $n$ 个数的积，记作 $P$ 。使用exgcd或者fermat小定理求出 $P$ 的逆元 $P^{-1}$。
那么，我们有 $P \cdot P^{-1} \equiv 1 \pmod{m}$ 。
变形一下，即： \(\frac{p}{a_i} \cdot a_i \cdot P^{-1} \equiv 1 \pmod{m}\)
可以看出，$\frac{p}{a_i} \cdot P^{-1}$ 就是 $a_i$ 的逆元。
我们预处理数组 ${a_n}$ 的前缀积 ${pre_n}$ 与后缀积 ${suf_n}$ ，于是 $\frac{p}{a_i}\equiv pre_{i-1} \cdot suf_{i + 1}$
这些过程都是线性的。
感觉dp不是很熟，之后需要加强训练，另外明天搞线段树。