CODE FESTIVAL 2016 Grand Final H - AB=C Problem
https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_h
問題
正方行列Cが与えられる。C=ABを満たすような正方行列のペア(A, B)はいくつあるか求めよ。
行列の要素の演算はすべて2で割った余りを取る。
解法
CとAに対して、行基本変形してもC=ABと(A, B)の個数が維持される。
CとBに対して、列基本変形しても同様。よって解はCのサイズNとランクRにのみ依存する。
Cのランクはガウスの消去法で求めることができる。
Cのj列目のベクトルは、A = (a1, ..., an) のN個の列ベクトルに係数を掛けて足したもので、その係数はBのj列目のベクトルである。
AのN個のベクトルがCの空間を張り、AのランクがSならば、Bのj列目の選び方はpow(2, N-S)通りである。N列あるので、Aが決まったあとのBの選び方はpow(2, N*(N-S))通り。
Cの空間を張るようなAを数える。
dp[i][j][k] := i個のベクトル(a1, ..., ai)の数、ただし
- (a1, ..., ai)のランクがj
- (a1, ..., ai)とCの共通部分のランクがk
初期値
dp[0][0][0] = 1;
i+1個目のベクトルの pow(2, N)通りは:
(1) j個の基底から作る場合 pow(2, j) 通り
dp[i+1][j][k] += dp[i][j][k] * pow(2, j);
(2) Cとの共通部分がないような線形独立なベクトルを作る場合、「Cの空間とj個の基底」から作ることができないベクトル。pow(2, N) - pow(2, R-k+j) 通り
dp[i+1][j+1][k] += dp[i][j][k] * (pow(2, N) - pow(2, R-k+j));
(3) Cとの共通部分がある線形独立なベクトル。pow(2, R-k+j) - pow(2, j) 通り
dp[i+1][j+1][k+1] += dp[i][j][k] * (pow(2, R-k+j) - pow(2, j));
Bの選び方を考えると、最終的な解は
for (j = R; j <= N; j++) ans += dp[N][j][R] * pow(2, N*(N-j));
