線形方程式・基底・分離可能変換へ変換する
概要
複数の条件を同時に満たす値を探す、与えられた値のXORで作れる値を調べる、配列全体に決まった変換をかける。この三つは線形代数で扱えるが、入力も求めるものも異なる。まず何を未知数とし、何を答えとして得たいかを分けよう。行列式による数え上げは別の単元で扱う。
考え方
制約を解くと、特解と動かせる方向が得られる
0か1の三つの未知数 に、次の条件を課してみる。
は排他的論理和(XOR)である。0と1を要素とし、加算・乗算を2で割った余りで行う体を と呼ぶ。この体の加算はXORなので、上の条件は連立一次方程式になる。
独立な条件の数である rank(階数) は2で、三つの未知数に対して自由に選べる値が一つ残る。条件を満たす一つの解を特解と呼び、この例では を選べる。右辺を両方0にした方程式の解集合が kernel(核) であり、この例では 一つを基底に持つ。基底とは、その組合せで集合の全要素を一意に表せる独立なベクトルの組である。
特解にkernelの要素を成分ごとにXORすると元の条件を保つ。したがって、全解は
となる。「一つ構成する」なら特解、「どれだけ動かせるか」ならkernel、「何通りか」なら自由度を使う。同じ消去結果でも、要求に応じて取り出すものが変わる。線形方程式・rankでは、この二式の行を実際に消去し、自由変数から両方の解を復元する。さらに条件を加えたとき、自由度が残っていても矛盾して解がなくなる場合を確かめる。
生成できる値と、値配列の変換を区別する
同じXORでも、ベクトルが入力として与えられ、その組合せでどの値を作れるかを聞かれることがある。一方、配列の各値が既知で、全体に線形変換をかけたい場合もある。次のように入力と欲しい結果を見比べると、進む子単元を選べる。
- 制約を満たす未知数を求める。 上の二式から、解の有無・特解・kernelの基底を得たいなら、線形方程式・rankへ進む。
- 与えられた値で作れる値を管理する。 入力が と なら、XORで作れる値は 、、、 の四つである。この集合を二本の基底で表す方法は、XOR線形基底で扱う。
- 値配列全体を決まった規則で変換する。 添字を2ビットで表す4要素の配列 に、各ビット方向の和・差の変換をかけると を得る。こうした配列全体の計算を軸ごとの小変換で行う方法は、分離可能線形変換・Walsh–Hadamard変換で扱う。
二つ目の例の二本は、最初の連立方程式の係数行でもある。ただし、制約を解くときは「各行との積和が指定された右辺になる未知ベクトル」を探し、基底を持つときは「入力ベクトルを選んでXORした結果」を表す。係数行の生成する集合とkernelは別の空間である。
三つ目の例では配列の並びを添字 の順とし、変換は整数の和・差で計算している。添字のビット演算と、配列の値の演算を混同しない。特にWalsh–Hadamard変換を逆に戻すには2で割れることが必要で、係数を にすると和と差が同じになり、元へ戻せない。各軸の小変換へ分けられる条件と具体的な更新は子単元で扱う。
成立条件と計算量
線形方程式の消去では、計算する係数が体をなし、選んだ非零のピボット(消去の基準にする係数)に逆元があることを確認する。合成数を法とする剰余では、非零でも割れない係数がある。
一般体の密行列消去とビット列のXOR消去では演算費用が違う。行数を 、列数を とすると、素朴な密行列消去は 回の体演算を使う。 の行はビット列としてまとめてXORできるが、複数語にまたがる行を定数時間とは数えない。XOR基底は値のビット長、分離可能変換は配列長と軸ごとの変換の大きさで費用を評価する。具体的な計算量は各子単元で確認する。
下位単元
- 線形方程式・rank — 青色
- XOR線形基底 — 青色
- 分離可能線形変換・Walsh–Hadamard変換 — 黄色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC220 H「Security Camera」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: 分離可能線形変換・Walsh–Hadamard変換
- ABC236 F「Spices」 公式問題主題: matroid greedy
技能・出典
主題: matroid greedy(独立集合族の交換公理を確認し、重み順に独立性oracleを通すgreedyが最適基底を作ることを証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: XOR線形基底(整数をF2 vectorとして最高bit pivotで消去し、独立性判定・最大XOR・表現可能性をonlineに保つ。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: matroid greedy / 補助タグ: XOR線形基底
- ABC265 Ex「No-capture Lance Game」 公式問題
技能・出典
主題: NTT・FFTで畳み込みと相互相関を求める(係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。)。既習技能: 独立な数ゲームの和(全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。) / 分離可能線形変換・Walsh–Hadamard変換(Kronecker積で表される多次元線形変換を各軸の小変換へ分離し、stride走査で正変換または逆変換を計算できる。)。主タグ: 畳み込み・相互相関 / 補助タグ: 独立な数ゲームの和、game状態・Grundy DP、分離可能線形変換・Walsh–Hadamard変換
- ABC299 Ex「Dice Sum Infinity」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 確率・期待値DP / 補助タグ: 線形遷移・行列累乗、線形方程式・rank、法上の四則演算・高速累乗・逆元
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ
技能・出典
主題: 行列式による数え上げ(辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。)。既習技能: factorial convolutionによる多項式Taylor shift(二項係数を階乗で分離し、係数列の反転と一回の畳み込みから P(x+a) の全係数を準線形時間で復元できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 行列式による数え上げ / 補助タグ: 線形方程式・rank、factorial convolutionによる多項式Taylor shift
- ABC399 G「Colorful Spanning Tree」 公式問題
技能・出典
主題: 線形matroid交差の乱択rank判定(二つの線形matroid表現から乱択intersection matrixを構成し、Schwartz–Zippelの誤り上界を示したうえでrankを最大共通独立sizeとして判定できる。)。既習技能: 乱択の成功条件と誤り確率を設計する(乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。) / 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 線形matroid交差の乱択rank判定 / 補助タグ: 線形方程式・rank、乱択・Monte Carloアルゴリズム
前提・学習成果・出典
導入対象の目安: 青色(1600–1999)。rank・基底・線形写像を制約と変換の共通言語として学ぶ入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-linear-algebra-xor
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 行列式による全域木・非交差pathの計数は行列式計数の単元で扱う。通常の多項式畳み込み・生成関数と、幾何の面積行列式も対象外とする。
根拠
- ABC276 Ex 公式問題文・公式解説 — 非零の積の条件を 上の連立一次方程式へ写す接続。二式の小例は本書の独自例。
- ABC212 H 公式解説
- ABC212 H 公式問題文
- ABC220 H 公式解説
- ABC220 H 公式問題文
- ABC223 H 公式解説
- ABC223 H 公式問題文