B 题 \mathcal O(nm^2p) 的 dp 是可以过的，考虑设 dp_{i,j,k,l} 表示在第 i 行第 j 列前面，当前行已经选了 k 个数且总和 \bmod p =l 的最大和。然后不难用刷表法列出转移式，再注意一下边界的转移即可。
C 题没想到用数据结构解。考虑用一个小根堆存下想要喝水的人，再用一个队列存排队喝水的人。观察一些性质可得队列里的人的编号是单调递减的。
剩下模拟即可，要注意一些细节（比如一个正在排队的人喝到了水，离开时，就可能有人想喝水等）。
10.4 训练报告
自己做出 A，B 两题，C 题看了原题的题解学会了。
A 题第 1 小问就是最短路，第 2 小问需要在最短路的基础上统计最大值。我一开始想的 bfs，但是为了统计最大值需要重复更新，而且是在线回答询问的，会 T 掉两个点。
不妨换一种思路，注意到 n \le 300，可以使用 \text{floyd} 离线求最短路，并且能够在三重循环的过程中顺带更新最大值。这样我们就可以 \mathcal O(1) 解决询问。
B 题一开始想的对于每个点 dfs 求三元环，其复杂度可以被卡成暴力的复杂度。考虑一个重要的性质对于一组 (x,y,z)，其中 y 是 x 的邻居，z 是 y 的邻居，z 是 x 的邻居。换言之，z 是另外两个点共同的邻居。那么首先以 \mathcal O(n^2) 枚举 x 和 y，满足 y 是 x 的邻居。然后计数它们共同的邻居 z。
所以考虑倒着做，每删一条边，我们就将边两端的点度数分别减一，如果删完之后出现了小于 k 的点，则继续拓扑删点。时间复杂度为 \mathcal O(n+m)。
10.5 训练报告
自己做出 A，B，C，D 题，E 题拿了 20 分。
订正出 F，G 题。
A 题直接二项式定理展开。答案为 C_k^{n} a^n b^m。
B 题同余式先转换成等式，然后 exgcd 求解，最后转成最小整数解（往上或下调整 k 个 b）即可。
C 题利用唯一分解定理展开，然后指数都乘上 b。此时每个质因数的贡献可以用等比数列求和公式快速计算，如果除数 \bmod 9901 的逆元不存在，那么把原式展开，发现此类贡献为 1，直接相加即可。
D 题发现 \mathcal O(nm) 的做法可以过。考虑在 [1,m] 中枚举解 x，然后用秦九韶 \mathcal O(n) 判定是否合法（不用秦九韶，累乘 x 计算也可做到 \mathcal O(n)）。接着发现似乎需要高精度，但那样输入会炸，直接考虑模一个大质数。设这个质数为 p，记原多项式为 f。如果 f(x) \bmod p =0，我们就认为 f(x) = 0，碰撞的概率很小，可以过。
E 题目前只会 \mathcal O(n) 暴力。
F 题有一个很关键的性质，即关键点。关键点指的是一个排列中不是其它数倍数的数。一个排列对答案的贡献即这个排列中最后一个关键点的位置。我们先埃筛出所有关键点，记关键点的个数为 sum。接着我们枚举最后一个关键点可能出现的位置，利用组合计算答案。最终答案为：
\sum\limits_{i = sum}^{n} i \times C(i-1，sum-1) \times sum! \times (n-sum)!
G 题要求 \sum\limits_{i=0}^{\infty} C_{nk}^{ik+r} \bmod p 的值。考察 C_{nk}^{ik+r} 的组合意义。在 nk 个物品中，选出 j 个物品的方案数，其中有 j \bmod k =r。简化这个组合数，设 f_{i,j} 表示在前 i 个物品中选 s 个，且 s \bmod k = j 的方案数。于是有递推式：