A题也可以直接在环 ${x+y\sqrt{b}\mid x,y\in Z}$ 上定义乘法
2021.9 月月赛题解
Once edited 3 年，3 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先，感谢以下同学为本次月赛命题做出的贡献：
命题人：上海交通大学 孙司宇
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。
最后，祝各位 ACMer 和 OIer 们开学快乐，学业有成。
扫描二维码关注我们的微信公众号，获得更多信息。本次月赛的获奖名单和后续竞赛通知将通过公众号发布。
A. Amazing Discovery
可以发现这是递推式
$$A_n = (2 * a) * A_{n-1} - (a^2 - b) * A_{n-2}$$
的通项，
其中
$$A_0 = 2, A_1 = 2 * a$$
矩阵快速幂即可。
B. Mine sweeper
每个格子代表 $3\times 3$ 大小的范围内所有地雷的数量，由于答案只需要求总地雷的数量，所以找到一组点恰好覆盖整张地图即可。实际上只需要上下以及左右每相隔三个选出一个即可，注意开始的位置保证不出现边界上只剩一行的情况。
C. Connection
不能通过第二种方法从 $0$ 变成 $1$ 的需要多花费 $1$。只需要计算有最少有多少个第一种情况。考虑把每一行每一列看成一个独立的点共 $(N+M)$ 个点，考虑点 $(x, y)$ 是 $1$，则把对应的行 $i$ 和列 $j$ 连接。那么可以看出，在同一个连通块内的边都可以通过情况 $2$ 得到。所以问题可以转化为连通块个数。
D. Divide and Merge
统计非 $1$ 奇数个数以及偶数，简单分类讨论
if(cnt0==0 && cnt1==0)
puts("Bob");
else if(cnt0%2 == 0)
puts("Alice");
else
puts("Bob");
E. Gradient
把所有点按延 $P/Q$ 投影的位置排序，斜率最接近 $P/Q$ 的两个点一定相邻。
证明：如果 $u$, $v$ 不相邻，取 $u$, $v$ 中间一点 $w$, $uw$, $wv$ 至少有一个斜率更接近 $P/Q$。
F. Traveling Frog
点分治，维护从分治中心到每个点路径上的方案书，合并 $O(K)$。
Comments
MAOoo
F题第二个数据是大数据吗，我的做法是在tarjanLCA的并查集过程中维护背包向量，理论复杂度应该是 $ O(K \alpha (KN + Q) $ 的，测了随机满数据跑了2。3s，但直接TLE2了。。
A题不就是奇/偶数项和吗
所以考虑用快速幂求解，但是发现 $b$ 不一定是二次剩余，所以要定义一个新的数域 ${x+y\sqrt{b}\mid x,y\in Z/(p)}$
对啊，但是直接二项式展开暴力算不是O(n)的吗
可以用分治来求，时间复杂度：$O(logn)$
哦哦，有道理