※ 引述《nicknick0630 (NICK)》之铭言：
: UVa 连结 :
: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2459
: 短网址 : https://is.gd/NYytBw
: 题目:
: 给一 N x N 的矩阵，里面每个元素皆为 0 或 1
: 且每个元素的 parity 定义为该元素位置的上、下、左、右四个位置中 1 的数目
: 题目要求我们要把其中一些 0 改成 1，让所有元素的 parity 皆为偶数
: 也就是 0、2、4个，并输出改变次数最少的值 ( 若无法的话输出 -1 )
: 解法:
: 列举出第一列，若题目给定的矩阵的第一列无法转换成列举的情况的话，删除此种情况
: 然后将所有合法的列举情况用第一列推导出第二列
: 再用 Row 2 推导出 Row 3，依序推导到 Row N
: 最后再用题目的矩阵与这些列举情况推导出来的矩阵做比较
: 找出最少 0 转换成 1 的次数
: 我的问题:
: 为什么可以保证 Row N 会是正确的? 也就是说 Row N 的 parity 也会是偶数个
: 若是考虑 Row 1 ~ Row N-1 ，因为都可以用他的下一列来修正
: 使自己一定为偶数 parity，但是 Row N 不能用 Row N+1 来修正自己
: 所以想请问要如何证明呢?
: 这是我写的文章，里面有更清楚的描述，我的问题就是在 "证明" 那一个段落
: 文章连结 : https://is.gd/eN7WyK
: 谢谢各位大大
: 感激不尽
用n=5来当范例思考
已知给定第一个row可以一路推到最后一个row(先不管正确与否) 且为唯一推法
也已知第一个row都是0的时候 可以得到一组符合条件的解
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
那可以试着每次flip一个位置就好 规则蛮容易看出来的 也会得到符合parity的解
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0
又已知 两个符合parity的解 xor 起来也会是一个符合parity的解
所以给定任意个第一个row 一定有办法是这n个解的xor组合 (且为唯一可能)