Topcoder-581

说好的 AFK 呢，还是忍不住参加了。

Solution

250 pts

慢慢码代码。不多说。

500 pts

考虑一条边 Ai-Bj 对答案的贡献。显然它一定会在一个环上，而且环的形状一定是 Ai --- At - Bs --- Bj ，可以得到 |Ai --- At| + |Bs --- Bj| = K - 2 。

然后枚举 \(i\) ，枚举 \(j\) ，统计所有到 \(i\) 距离为 \(a\) 的点数目为 \(cnt1_a\) ，统计所有到 j 距离为 b 的点数目为 \(cnt2_b\) 。那么 Ai - bj 对答案的贡献为 \(\sum_{a+b = K-2} cnt1_a cnt2_b\) 。

注意到一个环被算两次，除个 2 就好。

900 pts

由于每一列至多只能进行一种操作，所以我们 \(2^m\) 枚举每一列只允许哪一种操作。

假如我们知道了第一行的每个操作，那么我们可以依次推出剩下的每个格子的操作，因为第二行的操作要满足第一行的结果为 B ，所以第一行的操作也确定了，依次递推下去，可以知道后面每行的操作。我们只需要验证最后一行是否仍然满足要求即可。

所以在 \(2^m\) 枚举每一列允许哪种操作后，再枚举第一行每个操作。如果这里再 \(O(2^m)\) 枚举显然会 T 。考虑到这些操作应该是同一种操作，所以进行操作的若干个格子一定是进行同一种操作的若干个格子，我们只需要枚举两个集合的子集就好了。

总时间复杂度为 \(O(nm 3^m)\) 。

nonsense

一进来看到一个 ID 为 just.for.fun 。一看是 NFLS 的，但是不知道是谁。看命名风格有点像 blue.boy ，最后发现果然是 JZP 。亚历山大 >_<

最后 room #2, #1 显然是 just.for.fun 。

Division #33 涨了 rating 。这真是极好的。