bzoj3517翻硬币

又浪了一周。
本来这题是想抢bzoj的first blood的,但是因为太浪了没有抢到。
今天是早上跟主席扯了半天猎奇做法,快到12点的时候才扯出正常做法。
ym xy

最暴力的做法显然就是对每个格子设一个变量然后高斯消元。
浪了半天之后弄了个比较靠谱的猜想——方程组的可行解唯一,也就是说可行解就是反转次数最少的解。
然后搞了半天就弄出正解了。
先来看n是偶数这个条件,这个条件比较特殊,事实表明就算n是奇数,高斯消元依旧可以搞出可行解的。
那么n是偶数的条件就是——为了方便我们优化高斯消元的。
我们设未知数表示格子(i,j)是否被翻动。
我们用表示异或运算。
首先假设最后所以格子都翻为1,第i行第j列初始为
那么就有n*n个方程:

然后用脑洞思考一下。。。
第i行第1列的方程就是:

第i行第2列的方程就是

那么第i行第1列的方程异或上第i行第2列得到的方程就是

然后因为n是一个偶数……
假设是第i行所有格子翻动次数之和的奇偶性。
假设是第i列所有格子翻动次数之和的奇偶性。
那么第i行所有格子对应的方程全部异或起来之后。。。就得到了所有格子翻动次数异或的数值。
第i列所有格子对应的方程全部异或起来之后。。。就得到了所有格子翻动次数异或的数值。
为了简单起见,我们可以暴力枚举所有格子翻动次数的奇偶性。
然后我们就能得到所有的数值。
然后我们注意一下原本第i行第j列对应的方程就是——

那么每个都能得到……答案唯一也顺便证出来了。
然后判断一下合法性更新答案就可以了。

Comments

comments powered by Disqus