20210823省选组总结

两道计数+一道类似计数的题？

~~计数专题吗？~~

前两题是真的难想但非常好写，主要还是研究一下原理吧。

T3还不会QwQ

T1

令向下的点为 $1 $ ，向右的点为 (2) 。

首先每条左下--右上的对角线都是一样的格子，然后显然（似乎可以根据对角线相同用裴蜀定理？）有周期 (g=gcd(n,m)) 。

设一个周期内有 (t) 个 (2) 点。

然后根据对角线相同，我们发现对于相邻的两列，后一列的 (2) 点比前一列的 (2) 点要上移一行（循环），那么每个点一共会走 (m) 步。同时，我们发现一条路径是由当前列的 (i) 点走到下一列对应的 (i+1) 点，所以第一列的 (1) 号点必然会走到最后一列的 (m + 1) 号点，由于有上移，这时该点可能已经不是第 (m+1) 个点了，而是变成 (m + 1 - frac{m}{g}t) 号。

根据裴蜀定理，能够走满棋盘当且仅当 (gcd(frac{n}{g} t , m - frac{m}{g}t)) 。

T2

考虑对每个环随机一个权值到每条边，这样偶环的异或和为 (0) ，奇环的异或和为一条边的权值，我们的目标是找到满足异或和为所有奇环异或和的集合个数。

这个是必要条件但不充分（只要足够随机就充分了 bushi。

然后发现每个大奇环会由奇数个奇环和若干个偶环组成，于是只取最小奇环即可。

注意树上差分的时候要用子树和的形式，不然会造成额外影响。