N, M, K <= 10^5, 看起來超級無敵瘋狂
Observation 1: 假設知道第一行、第一列，全部就都可以推出來了（2^(N+M-1)種）
a11 a12 a13
a21
a31
假設前三個是a, b, c，這一個 d 就要是a ^ b ^ c ^ 1，如此才會讓 a^b^c^d = 1
（也就是題目的定義）
Observation 2:
在5*4的表格上，會長的如下圖所示，恰好是 X ^ 該行 ^ 該列 ^ (bool)(偶行偶列)
因此，假設已經有填過了，就會變成 a 與 b 之間的條件限制（如果一個是1另一個就是0之類的），如同2-sat一般，而且邊是雙向的，就像以前討論過的題目，可以直接用disjoint set去實現。但比較麻煩的是有可能a1, a2這些單個直接被設限制，雖然依照目前為止的公式就可以求解，但編程複雜度會較高。
Observation 3:
接下來，我們希望把規則化簡。我想的作法是這樣，把第一行全部 xor x，如此後面一大堆的 xor x 都消失了，當然這不會改變任何東西，只是當b1是 1 時可能會變 0 罷了。再者，可以發現大家都是兩個東西在 xor ，為了統一化，把第一列全部再 xor 一個 y，變成如下圖所示。答案則是依此計算岀符合條件的變量種類後，除以二。
如此一來規則就很簡單，直接給出code。
http://ideone.com/o9XFTY
沒有留言:
張貼留言