以下の解説では \(2^{M}\) 未満の整数とそのビットごとの排他的論理和 \(\oplus\) をベクトル空間 \(\mathbb{F}^M_{2}\) の元と加法とみなし、基底、一次独立など線形代数の用語を用います。

[1] 基底の個数の変化に着目

\(S\) の要素で貼られる部分空間の基底を \(e_1,\ e_2,\ \dots,\ e_n\ (e_i \in S)\) とします。 操作において基底が \(\{e_1,\ e_2,\ \dots,\ e_m\} \subset T_1,\ \{e_{m+1},\ e_{m+2},\ \dots,\ e_{n}\} \subset T_2\) という風に分けられたとすると、操作後は \(\{e_1 \oplus e_2,\ e_1 \oplus e_3,\ \dots,\ e_1 \oplus e_m,\ e_{m+1} \oplus e_{m+2},\ e_{m+1} \oplus e_{m+3},\ \dots,\ e_{m+1} \oplus e_{n} \} \subset S\) であり、これらの要素は一次独立であるため、操作後の \(S\) の基底は \(n-2\) 個以上です。

基底の個数の減らし方を考えます。例えば \(S\) の要素を \(e_i\) の線形結合で表す際、 \(e_1\) を用いるものを \(T_1\) 、それ以外を \(T_2\) という風に分けた場合を考えます。このとき操作後の \(S\) の要素は、 \(e_i\) の線形結合で表す際 \(e_1\) 以外のみを用いて表すことができるので、基底の個数は \(n-1\) 以下にできています。

[2] 基底を \(2\) 個減らせる条件

上記のようにして基底を \(1\) 個以上減らす方法はわかったので、あとは基底を \(2\) 個減らせる条件を考えればいいです。

基底を \(\{e_1,\ e_2,\ \dots,\ e_m\} \subset T_1,\ \{e_{m+1},\ e_{m+2},\ \dots,\ e_{n}\} \subset T_2\) という風に分けて操作することを考えると、操作後の基底が \(n-2\) 個になるには、 操作後の \(S\) のすべての要素が \(e_1 \oplus e_i\ (2 \leq i \leq m),\ e_{m+1} \oplus e_j\ (m+2 \leq j \leq n)\) の線形結合で表される必要があります。これは \(e_i\) の線形結合で表す際、

• \(e_1,\ e_2,\ \dots,\ e_m\) の使用個数が偶数個
• \(e_{m+1},\ e_{m+2},\ \dots,\ e_n\) の使用個数が偶数個

であることと同値です。

これを踏まえて操作での \(S\) の要素の振り分け方を考えます。まず \(e_1 \in T_1\) であるため、 \(T_1\) に振り分ける要素は \(e_i\) の線形結合で表す際

• \(e_1,\ e_2,\ \dots,\ e_m\) の使用個数が奇数個
• \(e_{m+1},\ e_{m+2},\ \dots,\ e_n\) の使用個数が偶数個

である必要があります。\(T_2\) に割り振る要素はその逆です。

以上より基底を \(2\) 個減らせるのは \(S\) の要素を \(e_i\) の線形結合で表す際、使用する個数が奇数個であることが必要十分条件です。とくに、\(1\) 回操作した後は必ず \(0 \in S\) が成り立つので、\(2\) 個減らせることがあるのは最初の操作だけです。

[3] まとめ

以上より初期状態での基底の個数を \(n\) として、\(n \leq 1\) のときは \(n\) 、[2] の条件を満たさないときは \(n\) 、[2] の条件を満たすときは \(n-1\) が答えになります。

基底を求めたり [2] の条件を満たすかの判定は、行列の掃き出し法により \(O(NM^2)\) で計算することができ、十分高速です。