AGC 011 题解
AB 水题= =
C
C 比 D 难诶 /kk
特——别好的题！二分图真香
$C = V - E + F$ 学呆了，用不到就有点难受= = ？
原图中的独立点是最好搞的，设独立点个数为 p，则贡献为 $np * 2 - p^2$
考虑题目条件：$(a, b)$ 到 $(c, d)$ 有边当且仅当 $a -> c$，$b -> d$，等价于 $a、b$ 同时移动了一步到达 $c、d$。因此推得状态 $(a, b)$ 能到达状态 $(c, d)$ ，显然当且仅当路径 $a -> c$ 和 $b -> d$ 的奇偶性相同。由此联想到二分图。
考虑“特征点”$(x, y)$ 即无法在新图连通块内到达 $(t, k)$ 使得 $t < x$ 或到达 $(x, z)$ 使得 $z < y$。可以理解为字典序最小。显然特征点个数就是连通块个数。
我们发现，特征点第一维 $x$ 必须是原图连通块中最小的点。第二维 $y$ 可以是最小的点。但如果 $y$ 所在连通块是二分图，且和所在连通块里的最小点 $z$ 不在同一边，就无法变成 $z$（ $(x, y) -> (x, z)$，$x -> x$ 的奇偶性可以看作偶，那么 $y -> z$ 的奇偶性如果是奇就不行）。
D
找规律发现滚一次球后串变为取反后左移一位，末尾补位A。大致原因就是
- A-> B 变成 A A->
- A-> A 变成 B A->
- 开头和结尾也符合规律
发现 2n 步（不是 n 步，因为串的奇偶性有影响）必然会把初始的串给替换掉（可以理解为一位一位溢出了，其中有至多 n 步是第一位为 A 的要弹回），串就变成了 ABABAB… 或者 BABABA… 的形式，讨论一下奇偶性就好了
E
咕咕
F
咕咕