AT_abc_271_f 总结
题目：AT_abc_271_f
链接：洛谷，AT，vjudge
题意
-
有 \(n \times n\) 的矩阵 \(a_{i,j}\)，问有几条从 \((1,1)\) 走到 \((n,n)\) 且异或和为 \(0\) 的方案数（只能向右或下走）。
-
数据范围：\(2 \le n \le 20, 0 \le a_{i,j} \le 2^{30}\)。
思路
暴力
搜每条路径，判断是否合法，时间复杂度：\(O(C_{2n - 2}^{n - 1})\)，这和从 \((1,1)\) 到 \((n,n)\) 的路径数相关，具体看这篇。显然超时
正解
-
我们发现这个题是不能使用 \(DP\) 的，因为 \(a_i\) 太大了。但是看到 \(n\) 比较小，可以想到搜索暴力，但是直接搜会超时，那该怎们办了？
-
这里有一种方法，叫做折半搜索（
Meeting in the middle）。就是搜两遍，我们从 \(1,1\) 开始搜，只要搜到一点在副对角线上，就停止。同样从 \(n,n\) 开始搜，搜到副对角线也停止。用map记录一下到副对角线的每个点每个值的方案数，在枚举相遇的点和从 \((1,1)\) 到当前点的异或和，那么从 \((n,n)\) 到当前点的异或和是确定的，出现次数相乘得到答案，再将这些答案加起来得到最终答案。 -
当然因为
map常数大，可以使用vector存贮到当前点的值，在枚举每个相遇的点，排个序，做一遍双指针或二分也可以得到答案（快得多）。 -
时间复杂度
- 从 \(1,1\) 到副对角线上的点走 \(n - 1\) 步，每步可以想右或下走，也就是：\(O(2^n)\)。
- 排序，双指针：\(O(2^n \log 2^n) = O(2^n n)\)。
- 总时间复杂度：\(O(2 ^ nn)\)。