この問題は解法が簡潔かつ面白いので、まず先に解法を説明して、その後に必要な知識の説明をしようと思います。

解法はきわめてシンプルです。\(X = \sum_i A_i\) とします。\(X\) が偶数の場合が解ければよいです。
次の条件を満たす \(X\) 頂点の辺重み付き無向グラフ \(H\) を考えます。

• 頂点には \(1\) 以上 \(N\) 以下の整数のラベルが貼られている。
  • 特に、整数 \(i\) のラベルが貼られた頂点はちょうど \(A_i\) 個ある。
• 同一のラベルが張られた頂点間には重み \(0\) の辺が張られている。
• \(G\) において \(i-j\) 間に辺があるときかつその時に限り、ラベル \(i\) が張られた頂点とラベル \(j\) が張られた頂点 \((i \neq j)\) の間に重み \(1\) の辺が張られている。

すると、実は \(H\) の最小重み完全マッチングを考えるだけでこの問題は解けています！すなわち、

• 最小重み完全マッチングが存在しない場合、良いグラフも存在せず、
• 最小重み完全マッチングが存在する場合、元の問題の答えは最小重み完全マッチングの重みと一致します。

この解法の正当性を確認することは \(H\) を思いつくことに比べれば難しくないので省略します。
よってこの問題は最小重み完全マッチングを計算できれば解けて、これは \(\mathrm{O}(X^4)\) や \(\mathrm{O}(X^3)\) 程度で計算できる(後述)ので十分高速です。

以上が解法となります。では次に、この問題を解くのに必要である、最小重み完全マッチング の重みを容易に計算する方法について解説します。

まず、教科書的なアルゴリズムについて説明します。最小重み完全マッチングは Edmonds の花アルゴリズム と呼ばれるアルゴリズムで \(\mathrm{O}(N^3)\) (\(N\) はグラフの頂点数) で計算できることが知られています。コンテスト中の正解者は、おそらくこのアルゴリズムを貼るか、あるいは Python の networkx モジュールなどからこのアルゴリズムを呼び出しているのではないかと予想しています。しかしこのアルゴリズムは実装が難解かつ長大であるとされていて、競技プログラミングにおいて想定解として登場することはほとんどありません。

実は最小重み完全マッチングは、その重みだけであれば Tutte 行列 および 多項式補間 を用いれば容易に計算できます。まずは Tutte 行列から見ていきましょう。

Tutte 行列と完全マッチング

グラフ \(G(V, E)\) (\(V=\lbrace 1,2,\dots,N \rbrace\)) の Tutte 行列 \((A_{i,j})\) とは、以下の成分を持つ \(N \times N\) 行列を言います。

\[ A_{i,j}= \begin{cases} x_{i,j} & \text{if } (i, j) \in E \text{ and } i \lt j \\ -x_{i,j} & \text{if } (i, j) \in E \text{ and } i \gt j \\ 0 & \mathrm{otherwise} \\ \end{cases} \]

Tutte 行列の重要な性質として、次の性質があげられます。

次の \(2\) つの命題は同値である。

• Tutte 行列 \(A\) の行列式が (\(x_{i,j}\) を変数とする多項式として) 非ゼロである
• \(G\) が完全マッチングを持つ

(証明) \(A\) の行列式 \(\det A\) は次の式で定義されます。ここで \(S_N\) はサイズ \(N\) の置換全体からなる集合で、\(\mathrm{sgn}(\sigma)\) は置換 \(\sigma\) が偶置換であれば \(1\) 、奇置換であれば \(-1\) を取る関数とします。

\[\det A = \sum_{\sigma \in S_N} \mathrm{sgn}(\sigma) A_{1,\sigma(1)} A_{2, \sigma(2)} \dots A_{N, \sigma(N)}\]

置換 \(\sigma\) に対応する項について考えましょう。この時 \(\sigma\) の順列グラフ (\(i \to \sigma(i)\) に辺を貼った \(N\) 頂点 \(N\) 辺の有向グラフ) はいくつかのサイクルをなします。 このグラフが奇閉路を持つと仮定します。この時、「全ての奇閉路に含まれる頂点のうち頂点番号が最小の頂点」が含まれる奇閉路を選び、その閉路に含まれる辺の向きを全て逆にします。そうしてできるグラフに対応する置換を \(\sigma'\) とします。この時、\(\sigma\) の \(\det A\) への寄与と \(\sigma'\) の \(\det A\) への寄与は \(-1\) 倍の関係になることが確認できます。(\(\sigma\) から \(\sigma'\) への変換は偶置換なので \(\mathrm{sgn}\) は無視できて、\(A_{\ast,\ast}\) が \((-1)^{(奇閉路長)}\) 倍される) \(\sigma\) と \(\sigma'\) は一対一対応であることも合わせると、結局奇閉路を含む項はキャンセルされて \(\det A\) に含まれないことが確認できました。また、逆に \(\sigma\) が偶閉路のみを持つ時、この項はキャンセルされないことも確認できます。(キャンセルとしたらサイクルを反転した場合だが、偶閉路を反転しても寄与は等しいため)

以上の議論を踏まえると、同値性は以下のように証明できます。

• \((\to)\) : \(\det A\) が非ゼロの場合、ある置換 \(\sigma\) であって \(\det A\) への寄与が非ゼロかつ順列グラフが偶閉路のみからなるものが存在する。この時、偶閉路を \(1\) 辺飛ばしで取ることで完全マッチングを得られる。
  
• \((\gets)\) : 完全マッチングを \((a_1, b_1), \dots, (a_{N/2}, b_{N/2})\) とすると \(\sigma(a_i) = b_i, \sigma(b_i) = a_i\) を満たす置換 \(\sigma\) に対応する項はキャンセルされないので \(\det A\) は非ゼロである。

よって 2 つの命題は同値であることが証明できました。(証明終わり)

Tutte 行列の性質を利用すると、\(E\) 変数の行列式が非ゼロであるか計算できれば完全マッチングの存在判定ができることがわかります。この計算は直接は難しいですが、このような場合は乱択を利用すれば非ゼロかどうかを高確率で判定できます。すなわち、十分大きい素数 \(P\) を取ってきて \(x_{i,j}\) に乱数を代入した時の行列式を計算すればよいです。この乱択が失敗する確率は Schwarz-Zippel lemma を利用すれば \(\mathrm{O}(N / P)\) で抑えられます。
以上の議論により、Tutte 行列を利用すれば完全マッチングの存在判定が容易にできることがわかりました。計算量は行列式を計算する部分がボトルネックで、掃き出し法を用いた場合 \(\mathrm{O}(N^3)\) となります。

Bonus 1: Tutte 行列の性質として次の事実も成り立ちます。正当性を考えてみましょう。

• \(x_{i,j}\) に乱数を代入した時の \(A\) の \(\text{mod }P\) 上の rank は \(G\) の最大マッチングのサイズと高確率で一致する。

Bonus 2: 線形代数の知識を応用すると、Tutte 行列を利用して \(\mathrm{O}(N^3)\) で完全マッチングを復元できることが知られています。興味がある人は考えてみましょう。(かなり難しいです)

最小重み完全マッチング

Tutte 行列を利用した完全マッチング判定は、少し変形することで最小重み完全マッチングの重みの計算に応用できます。簡単に説明すると、Tutte 行列に辺重みへ対応する変数 \(y\) を追加してある種の母関数として解釈すればよいです。

具体的に説明します。辺重み付きグラフ \(G(V,E)\) の辺 \(ij\) の辺重みを \(w_{i,j}\) とします。(\(w_{i,j}\) は非負とします) 行列 \(B\) を次のように定義します。

\[ B_{i,j}= \begin{cases} x_{i,j} y^{w_{i,j}} & \text{if } (i, j) \in E \text{ and } i \lt j \\ -x_{i,j} y^{w_{i,j}} & \text{if } (i, j) \in E \text{ and } i \gt j \\ 0 & \mathrm{otherwise} \\ \end{cases} \]

この時、\(G\) の最小重み完全マッチングの重みは次のようになります。

• \(B\) の行列式が(多項式として)ゼロである場合、完全マッチングは存在しない。
• \(B\) の行列式が非ゼロである場合、項のうち \(y\) の次数が最小のものを取り出して、その次数を \(2\) で割ったものが最小重み完全マッチングの重みとなる。

(証明) \(B\) の行列式が(多項式として)ゼロである場合に完全マッチングは存在しないことは Tutte 行列の性質から明らかです。
後者を証明します。\(G\) の最小重み完全マッチングに対応する項の \(y\) の次数が重みの \(2\) 倍と一致することは明らかなので、より \(y\) の次数が小さい非ゼロ項が存在しないことを言えばよいです。

非ゼロ項に対応する \(\sigma\) を任意に取ります。\(\sigma\) の順列グラフは偶閉路のみからなります。サイズが \(4\) 以上の偶閉路を 1 つ取り \(v_1 \to v_2 \to \dots \to v_{2n} \to v_1\) とします。\(\sigma\) に対して以下の操作を行います。

• \(w_{v_1, v_2} + w_{v_3, v_4} + \dots + w_{v_{2n-1},v_{2n}}\) と \(w_{v_2, v_3} + w_{v_4, v_5} + \dots + w_{v_{2n}, v_1}\) の大小を比較する。
• 前者が小さい場合、偶閉路を \(v_1 \to v_2 \to v_1\), \(v_3 \to v_4 \to v_3, \dots, v_{2n-1} \to v_{2n} \to v_{2n-1}\) に張り替える。　
• そうでない場合、偶閉路を \(v_2 \to v_3 \to v_2\), \(v_4 \to v_5 \to v_4, \dots, v_{2n} \to v_1 \to v_{2n}\) に張り替える。　

この操作を繰り返すと、\(y\) の次数が等しいか小さくなる方向に変形し続けるだだけで \(\sigma\) をその順列グラフがサイズ \(2\) の閉路のみからなるものに変形できます。この最終的な \(\sigma\) に対応する非ゼロ項の \(y\) の次数が最小重み完全マッチングの重みの \(2\) 倍よりも小さいと、最小重み完全マッチングよりも重みの小さい完全マッチングが存在することになるので矛盾します。よってこの項の \(y\) の次数は最小重み完全マッチングの重みの \(2\) 倍以上です。よって元の \(\sigma\) に対応する項の \(y\) の次数もまた最小重み完全マッチングの重み以上となります。以上より証明が完了しました。(証明終わり)

よって、多項式行列の行列式のうち \(y\) の次数が最小である項の \(y\) の次数が計算できれば最小重み完全マッチングの重みが計算できることになります。Tutte 多項式の例と同様に \(\text{mod }p\) 上で \(x_{i,j}\) に乱数を代入すると、\(y\) のみを変数に持つ行列 \(C\) の行列式を計算する問題になります。 確率的な理論保証は前と同様に Schwarz-Zippel lemma で保証可能です。
\(C\) の行列式の \(y\) の次数の最大値は、\(G\) の辺重みの最大値を \(W\) として \(WN\) になります。すなわち \(C\) の行列式は \(WN\) 次以下の \(y\) の多項式です。よって、\(C\) に \(y=0,1,\dots,WN\) を代入して得られる値を多項式補間すれば行列式が計算できます。計算量は行列式を \(WN+1\) 回計算する部分がボトルネックで \(\mathrm{O}(WN^4)\) になります。

これは余談ですが、多項式補間の実装をしたくない場合は離散フーリエ変換を使用して多項式を復元することも可能です。すなわち、多項式の次数 \(N\) よりも大きい整数 \(B\) を取って、\(1\) の \(B\) 乗根を \(\zeta\) として \(y=\zeta^0, \zeta^1, \dots, \zeta^{B-1}\) で多項式の値を評価して、 \(\mathrm{O}(B^2)\) で逆フーリエ変換をすれば元の多項式が求められます。また、\(p\) を NTT-friendly mod として \(B\) を \(2\) 冪とすれば(基数 2 の)高速フーリエ変換で \(\mathrm{O}(B \log B)\) で計算することもできます。
このテクニックはフーリエ変換・逆フーリエ変換の定義式さえ覚えていれば使用できるので、Tutte 行列に限らず「ICPC で多項式の復元が必要になったがライブラリに入れ忘れた」というシチュエーションで使えます。是非機会があったら使用してください。

Bonus 3: この手法を少し変形すれば、完全マッチングに限らない一般の最大重みマッチングにも応用できます。(最小重みマッチングでも使えますが、そもそもこれは常に答えが \(0\) です) どのように変形するか考えてみましょう。

以上が行列演算を用いて最小重み完全マッチングの重みを計算する手法になります。今回の問題では辺重みが \(0,1\) のグラフの最小重み完全マッチングを計算できれば良く、上記の手法を適用すれば計算量 \(\mathrm{O}(N^4)\) で計算できます。なお、ABC323G で登場した \(\det(Ax+B)\) を高速に計算する手法 を用いれば計算量を \(\mathrm{O}(N^3)\) に落とすこともできます。

一般グラフにおける完全マッチングや最大マッチングを計算する問題は、前述の通り AtCoder では出題されないと考えられるジャンルです。しかし、今回解説したように、完全マッチングや最大マッチングはそのサイズだけであれば(数え上げ関連のアルゴリズムに熟達していれば)ただちに計算できます。5 時間コンテストでもごくまれに最大マッチングへの帰着を要求されるので、グラフ関連の分野に強くなりたい人はぜひ今回の問題を学習してみてください。