linear_equation.hpp ファイル

#include "../../kyopro_library/template.hpp"

[ソースコード]

関数
template<int MAX_COL>
int	RowReduction (vector< bitset< MAX_COL > > &a, int col, vector< int > &where)
	F_2 上の連立線形方程式 https://mathlandscape.com/solution-sp/ https://yukicoder.me/submissions/1011997 verify: https://yukicoder.me/problems/no/2895 verify: https://yukicoder.me/problems/no/3229 verify: https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2
template<int MAX_COL, bool ONE_KER = false>
int	LinearEquation (vector< bitset< MAX_COL > > a, vector< bool > b, int col, vector< bool > &x0, vector< vector< bool > > &ker)
	連立線形方程式 Ax=b を解く

関数詳解

RowReduction()

template<int MAX_COL>

int RowReduction	(	vector< bitset< MAX_COL > > &	a,
		int	col,
		vector< int > &	where )

F_2 上の連立線形方程式 https://mathlandscape.com/solution-sp/ https://yukicoder.me/submissions/1011997 verify: https://yukicoder.me/problems/no/2895 verify: https://yukicoder.me/problems/no/3229 verify: https://judge.yosupo.jp/problem/system_of_linear_equations_mod_2

掃き出し法

引数

a	連立方程式 Ax=b の拡大係数行列
col	拡大係数行列の列数
where	ピボットとなる変数を記録するための配列

戻り値

A のランク

linear_equation.hpp の 16 行目に定義があります。

LinearEquation()

template<int MAX_COL, bool ONE_KER = false>

int LinearEquation	(	vector< bitset< MAX_COL > >	a,
		vector< bool >	b,
		int	col,
		vector< bool > &	x0,
		vector< vector< bool > > &	ker )

連立線形方程式 Ax=b を解く

引数

col	連立方程式の変数の数
x0	特殊解(b=0 の場合は自明解になる)
ker	Ax=0 の解空間の基底
ONE_KER	基底のサイズが巨大な場合、基底を1つだけ求められれば良いときはtrue

覚え書き

一般解は x0 と解空間の基底の任意の線形結合で表される

注意

A のサイズによっては基底のサイズが巨大になるので注意すること

linear_equation.hpp の 41 行目に定義があります。