题目质量不错（至少所有题目都有人过，是吧？）。
出题人之一 (ultmaster) 遗憾地表示：
这届水平不行啊。。。
EOJ Monthly 2017.12 题解
ultmaster edited 7 年前
A.
Prepared by kblack.
计算每一个点数模 $p$ 能达到的概率，直接暴力比较即可。
B.
Prepared by kblack.
虽然限制只能走马步，但我们很容易意识到在足够大的棋盘（例如象棋棋盘）上，马可以达到任何位置。事实上通过简单的验证，可以发现这一大小的下界是 $3 \times 4$。
于是对于所有 $\geq 3 \times 4$ 的棋盘，我们可以断言所有砖之间可以互相到达，此时答案为 $nm \choose 2$。
当棋盘大小为 $3 \times 3$ 时，通过简单的模拟可以发现外围的 $8$ 块砖可以互相到达，此时答案为 $8 \choose 2$。
当棋盘大小为 $2 \times n$ 时，我们发现不同奇偶不同的行/列交替可达，此时有 2 组 $\lfloor n/2 \rfloor$ 的联通块与两组 $n-\lfloor n/2 \rfloor$ 的联通块，答案为 $2 \times {\lfloor n/2 \rfloor \choose 2}+2 \times {n-\lfloor n/2 \rfloor \choose 2}$。
当棋盘大小为 $1 \times n$ 时，没有合法的马步，此时答案为 $0$。
注意答案可能超过 $2147483647$，需要使用 long long 类型。
C.
Prepared by ultmaster.
我们可以先考虑字符串有序的情况，比如是 aaabcc，我们只要将字符串右移 3 位，变成 bccaaa，就做完了。那么对于无序的情况，我们可以通过排序让它有序，做完之后再排回去。
显然最多的字母出现次数大于一半的情况是不行的。否则就将每个字母的位置和字母绑定一下，按字母序对结构体进行排序。然后右移「出现最多的字母出现次数」位，再排回来就可以了。时间复杂度 $O(n \log n)$。
也可以对 26 个字母进行遍历，把每个字母填到合适的位置。具体细节留给读者思考。
D.
Prepared by infiniteee.
又到了喜闻乐见的套路题时刻。
一个很显然的想法是对左边的 $n$ 轮和右边个质因数之间建边，便是一个二分图，就是做匹配。但是很遗憾，朴素的匹配是错误的，因为存在一个顺序问题。正确的做法是有一次如果不能找到匹配，就直接跳出。这是一个非常经典的问题，具体证明可以自行搜索 BZOJ 锦囊问题。
求素数可以使用朴素的 $O(\sqrt{n})$ 做法，用素数筛筛过头了可能反而会超时。因为素数不多，但素数的范围比较大，如果直接照抄板子每次都 memset 可能会超时，可以打时间戳，或者直接对质数进行离散化。
也可以二分答案直接跑二分图，姿势好一点也能过。
E.
Prepared by kblack.
Easy 部分可以简单的用 $dp[i][j][k]$: 买个 $i$ 根，最后一天买 $j$ 根，买 $j$ 根已经 $k$ 天来实现。朴素转移时间复杂度 $O(n^4)$ 足够通过，可是没人做。
可以发现，购买棒棒糖，相当于是在做最大容量为 $n$，物品大小为 $ x, x+1, \ldots, n $ 的 $k$ 重背包，恰好使用 $m$ 元的方案数即是背包容量为 $m$ 的方案数，多重背包 $O(n^2k)$ 的复杂度明显是我们无法接受的，考虑使用生成函数优化背包。
$\prod_{i=x}^{n}(1+x^i+x^{2i}+\ldots+x^{(k-1)i})$
$= \prod_{i=x}^{n}\frac{1-x^{ki}}{1-x^i}$
$= \prod_{i=x}^{n}({1-x^{ki}}) \cdot \prod_{i=x}^{n}\frac{1}{1-x^i}$
$= \prod_{i=x}^{n}({1-x^{ki}}) \cdot \prod_{i=x}^{n}(1+x^i+x^{2i}+x^{3i}+\ldots)$
答案即是这个生成多项式的 $x^1$ 到 $x^n$ 的系数之和。
注意到第一部分可以由一次简单的 01 背包实现，复杂度 $O(n^2)$，第二部分可以由一次简单的无限制多重背包实现，复杂度 $O(n^2)$。
F.
Prepared by ???.
不知道什么地方挖出来的一道题目，稍微改了下。可能是原题啊。如果有人知道来源的话不妨透露下啊？
Easy 可以简单地跑一遍 Floyd，然后发现是一个线性方程组，然后跑一下 Gauss Elimination。Done！
注意 printf("%.0f") 是不对的！会输出 -0！
我们不难留意到一个事实，对于一条边上的两个点，我们做一次减法，得到的就是这条边所连的两个连通块的和的差值。假设该树以 1 为根，我们记第 $i$ 个节点的子树和与除了这个子树外其余节点的和的差为 $t_i$，假如说我们知道整棵树的和 $S$，那么 $S+t_i$ 就是两倍的子树和（可以自行验证）。
那么我们怎么求 $S$ 呢？可以发现，$\sum_{i=2}^n \frac{S + t_i}{2}$ 恰好等于 $p_1$，因为距离为 $1$ 的点恰好累积了一次，距离为 $i$ 的点恰好被累积了 $i$ 次。（也可以自行验证）。
那么利用这一个方程我们就可以解出 $S$，然后再跑一遍 dfs 求每个节点上的值就做好了。时间复杂度 $O(n)$。
有一个坑点是，本题数据范围没有给，需要从答案的范围反推数据范围，很显然要开 64 位整数。
G.
Prepared by BelowLuminous.
考虑离线处理。将所有查询和母串相连建后缀数组。对于每一个查询，在排好序的后缀数组中恰好有一段相对应，可以二分求得 $L,R$。问题就转换为在 $L,R$ 区间内有多少后缀的下标在查询区间范围内的。这是一个非常经典的区间问题。继续考虑离线处理，从大往小将数插入，然后使用树状数组轻松解决。时间复杂度 $O(n \log n)$。
事实上本题的做法非常套路，所以过得人也比 F 多（？？？）。
据验题人说暴力加疯狂特判也能过，而且玄学优化不可卡。暴力姿势太大，比不来。
Comments
原创。
如有雷同，那也没有办法，毕竟比较裸。