Description

Input

Output

Sample Input

Sample Output

Data Constraint

Solution

• （附：本人第 100 篇博文，為 OI 事業(yè)奮斗，多多支持~）。

• 這道題的題面讓人感到云里霧里，但是經(jīng)過仔細(xì)的抽絲剝繭之后就會發(fā)現(xiàn)這真“模型”。

• 首先， X 矩陣是由 Y 向量構(gòu)造出來的： X[i][j]=y[i]?xor?y[j] 。

• 所以當(dāng) X 矩陣的對角線上存在 1 時，就不合法了，輸出“-1”（異或運算的性質(zhì)）。

• 又由于 X 矩陣的對稱性，我們只需處理對角線上方的答案，最后乘2即可。

• 我們發(fā)現(xiàn)，如果每一位 A[i][j]=1 的話，因為 A?||?!X=!O ，所以要求 X[i][j]=1 。

• 所以相當(dāng)于 y[i]≠y[j] ，則點 i 向點 j 連一條無向邊，表示點 i 和點 j 為對立點。

• 這樣便構(gòu)出了一張二分圖（若有奇環(huán)則判為“-1”），用 Friend-Enemy 并查集 維護(hù)出聯(lián)通塊。

• 那么最后答案是所有聯(lián)通塊的 0 的個數(shù)乘 1 的個數(shù) 。

• 為了保證答案最優(yōu)，對于這些連通塊，我們可以做一遍類似背包的 O(N2)DP：

• 設(shè) F[i][j] 表示做到第 i 個連通塊、0 的個數(shù)為 j 的 1 的最大個數(shù) ，轉(zhuǎn)移顯然。

• 由于 X 取過反 ， 1 的最大個數(shù)即為所求。

• 又由于開始的狀態(tài)有 1 ，會計算重復(fù)，我們減去算出的 連邊條數(shù)（意義相同） 即可。

• 那么連邊、DP復(fù)雜度相等，這樣總時間復(fù)雜度即為 O(N2) 。