👏
外積代数 in 競プロ

2025/12/10に公開
話は聞いたことあったけど、競プロで見たことなかったので驚いた

 問題N 頂点 M 辺の無向グラフがあり、各辺には 1, \ldots, K の色のいずれかがついている。多重辺はありうる。色をいくつか選んで、N 頂点を連結にしたい。最小で何色選べば可能ですか？
N \leq 16, M \leq 200, K \leq 200
出典元Universal Cup 4-7 F: Challenge NPC II (link) を簡易化したもの

 難しさ色を前から見ていって選ぶか選ばないか決めるDPをすることを考えると、dp[現在のつながり方] = 最小の色数 としたくなる。

"つながり方" というのは N 頂点を集合に分割する方法に対応するので、その方法は \text{Bell}_N 通りある。

\text{Bell}_{16} \geq 10^{10} なので、このままだと厳しいし、この方針だと状態もこれ以上削ることは出来ない。

 アイデアまず問題の条件を、「色をいくつか選んで、その色の辺の中から N-1 本を選び、N 頂点を連結にする」と言い換える。
辺 (x,y) を N 次元の (\mathbb{R} なり \mathbb{Z}/p\mathbb{Z} なりの) ベクトル (0,\ldots,0,\overset{x}{1},0,\ldots,0,\overset{y}{-1},0,\ldots,0) とみなすと、

「辺の集合が森(サイクルがない) \Leftrightarrow それらのベクトルが線形独立」

が成立する (ここまではよくある)。
現状のアイデアだと、選ぶ/選ばないの状態の重ね合わせみたいなことはできない。

もし仮に、辺集合 \{e_1, e_2, \ldots, e_m\} に対して、

e_1 \times e_2 \times \cdots \times e_m みたいな謎の "計算" が出来て、
その結果が、「辺集合が線形独立かどうか？」を表す、というような構造があったら、

(1+e_1) \times (1+e_2) \times \cdots \times (1+e_m) という "計算" をすることで選ぶ/選ばないの 2^m 通りの状態を重ね合わせられている雰囲気になる
かなり都合のいい妄想を言っているが、この条件を満たす代数的な演算 \wedge が、外積, wedge product と呼ばれるものです。
数学っぽい説明と競プロっぽい説明を置いたので、好きな方を見てください。

 外積代数n 次元 K-ベクトル空間 V の基底ベクトル e_1, \ldots, e_n を固定する。(辺と変数が被ってるけど別の話です)
すると、外積代数 \wedge(V) は、e_{i_1} \wedge e_{i_2} \wedge \cdots \wedge e_{i_k} (1 \leq i_1 < i_2 < \cdots < i_k \leq n) を基底とする 2^n 次元 K-ベクトル空間となる。
(以降この基底を、 S = \{i_1, i_2, \ldots, i_k\} として e_S とも書くことにする)
ここに wedge product \wedge: \wedge(V) \times \wedge(V) \to \wedge(V) が次のように入る
双線型。なので基底同士の積を定義すれば良い
e_i \wedge e_i = 0
e_i \wedge e_j = - e_j \wedge e_i
結合的 (\wedge の連続を好きな順で計算して良い)
これらのことから、

e_S \wedge e_T = \begin{cases}
0 & \text{if } S \cap T \neq \emptyset \\
\text{sign}(S,T) \cdot e_{S \cup T} & \text{if } S \cap T = \emptyset
\end{cases}
となることがわかる。

ただし、\text{sign}(S,T) は S, T をこの順に並べてソートしたときの転倒数の parity が偶数なら 1, 奇数なら -1 となる関数。
F: V \to \wedge(V) への埋め込みが次のように定義できる
線形、なので F(e_i) だけ定義すれば良い
F(e_i) = e_i
同一視してしまって、F(v) を単に v と書くこともある。
\wedge^k(V) は index のサイズが k のやつらからなる部分空間で、定義より明らかに \wedge: \wedge^k(V) \times \wedge^l(V) \to \wedge^{k+l}(V) をみたす。ただし k+l > n のとき \wedge^{k+l}(V) = \{0\} とみなすことにする。
大事な性質として、元の空間 V のベクトル v_1, \ldots, v_k に対して、「v_1 \wedge v_2 \wedge \cdots \wedge v_k = 0 \Leftrightarrow \{v_1, \ldots, v_k\} は線形従属」 が成立する。
証明の雰囲気
(\Rightarrow) v_1, \ldots, v_k が線形従属なら、ある i について v_i = \sum_{j \neq i} a_j v_j と書ける。これを v_1 \wedge \cdots \wedge v_k の中の v_i に代入して展開すると、各項に同じベクトルが2回以上現れるので 0 になる。
(\Leftarrow) 自明ではないが、v_1, \ldots, v_k で貼られる空間を考えたり基底変換をすることで、v_1, \ldots, v_k が基底であるケースに帰着され、示せる。

よって V のベクトル (を F で送ったもの) の積を見ると、
線形独立かどうか
もし独立なら、何個ベクトルをかけたか
がわかる。

 競プロ勢向け説明サイズ n のベクトル a = (a_0, a_1, \ldots, a_{n-1}) を、サイズ 2^n のベクトル A = (A_0, A_1, \ldots, A_{2^n-1}) に変換する関数 F を次のように定義する:
vector<mint> F(vector<mint> a, int n){
	vector<mint> A(1<<n);
	rep(i,n) A[1<<i] = a[i];
	return A;
}
次に、サイズ 2^n のベクトル A, B に対して、サイズ 2^n のベクトル A \wedge B を次のように定義する:
vector<mint> wedge(vector<mint> A, vector<mint> B, int n){
	vector<mint> C(1<<n);
	rep(s1,1<<n) rep(s2,1<<n){
		if(s1 & s2) continue;
		int s3 = s1 | s2;
		// inv: s1 の中の要素と s2 の中の要素の間の転倒数
		int inv = 0;
		rep(i,n) for(int j=i+1;j<n;j++) if( (s1&1<<j) && (s2&1<<i) ) inv++;
		int sign = (inv%2==0) ? 1 : -1;
		C[s3] += A[s1] * B[s2] * sign;
	}
	return C;
}
このとき、サイズ n のベクトル v_1, v_2, \ldots, v_k に対して、

v_1, v_2, \ldots, v_k が線形従属ならば、F(v_1) \wedge F(v_2) \wedge \cdots \wedge F(v_k) = (0, \ldots, 0)

v_1, v_2, \ldots, v_k が線形独立ならば、F(v_1) \wedge F(v_2) \wedge \cdots \wedge F(v_k) \neq (0, \ldots, 0) かつ、popcount が k じゃないところの値はすべて 0
が成立する。
辺集合 E := \{e_1, e_2, \ldots, e_m\} に対して、W_E := (1 + r_1F(e_1)) \wedge (1 + r_2F(e_2)) \wedge \cdots \wedge (1 + r_mF(e_m)) を計算することにする。ここで、r_i は辺 e_i ごとにランダムに選んだ乱数。
1 + r_iF(e_i) というのは、長さ 2^n のベクトルであって、[0] = 1, [2^x] = r_i, [2^y] = -r_i, 他は 0 というやつです
すると、展開した各項がどの辺を選んだかの集合に対応していることを考えると、
「E の中からどのように n-1 本選んでも線形独立に出来ない」なら、すべての \text{popcount}(S) = n-1 な S に対し、W_E[S] = 0
となることがわかる。逆に、
「E の中からうまく n-1 本選んで線形独立にできる」なら、ある \text{popcount}(S) = n-1 な S が存在し、W_E[S] \neq 0 が高確率で期待できる。
なぜなら条件を満たす選び方に対応した項について、ある [\text{popcountが}n-1 \text{な}S] 成分が non-0 になる。乱数をかけているので、他の項が打ち消しあって 0 になる確率は低い。

 問題の解法各色 c について、W_{\text{色}c\text{の辺集合}} を計算しておく。以降、これを W_c と書く。

k 色でできるかの判定は、色を k 個選ぶすべての方法を試して、その中の一つに (W_{c_1} \wedge W_{c_2} \wedge \cdots \wedge W_{c_k})[\text{popcountが}N-1 \text{な}S] \neq 0 となるものがあるかを調べれば良い。が、これも上と同じような理由で、k 個選ぶすべての方法に対してのこの和をみればよい。
つまり、x を変数として、

(1 + xW_{0}) \wedge (1 + xW_{1}) \wedge \cdots \wedge (1 + xW_{K-1}) を計算し、これを展開したときの x^k の係数の [\text{popcountが}N-1 \text{な}S] 成分が non-0 かどうかを見れば良い。non-0 なら、色を k 個選んで N 頂点を連結にできる方法が存在する。
なので DP すればよい。色を前から見ていき、dp[k] をこれまで k 色選んだときの和とする。(色を N 個以上選ぶ必要はないので、k = 0, 1, \ldots, N-1 までで良い)

\text{next}[k] \gets \text{next}[k] + dp[k] (色を選ばない場合)
\text{next}[k+1] \gets \text{next}[k+1] + dp[k] \wedge W_c
という遷移を各色 c について行い、最後に dp[k][\text{popcountが}N-1 \text{な}S] \neq 0 となる最小の k を答えれば良い。
陽に W_c を計算してから dp にかけてしまうと、毎回の dp[k] \wedge W_c の計算に O(4^N) かかってしまうが、dp[k] \wedge (1 + r_1F(e_1)) のように辺を一つずつかけていく形にすれば、各辺ごとに O(2^N) で済む (1 + r_1F(e_1) の non-0 成分は高々 3 個なので)。よって全体で O(N \cdot M \cdot 2^N) で間に合う。
ちなみに元の問題ではもう少し一般化されていて、N 頂点を連結にするのではなく、各 k=1, \ldots, N について、連結成分の個数を k 個以下にする最小の色数を求める、という問題になっているので、考えてみてください。
問題

難しさ

アイデア

外積代数

競プロ勢向け説明

問題の解法

Discussion
