AOJ Graph Automata Player
AOJ Graph Automata Player
Graph Automata Player | Aizu Online Judge
感想
ICPCのチーム練習で解いた。好きな感じの問題なので、じーーっと考察していると解法がわかった。
解法
ある頂点に注目して考える。ある状態から次の状態に遷移するとき、その頂点から移動可能な点に書かれた数の総和が奇数であるとき、その頂点は$\ 1\ $になる、という風に読み替えるとわかりやすい。よく考えると、この頂点から(自分を含む)(他の各頂点に対して接続しているかどうか)の情報列と、(各頂点の値)の情報列の内積のようなもの(?)をとれば、その総和が計算できる。このことから、隣接行列を$\ G\ $、時刻$\ t\ $での状態を$\ S_{t}\ $、時刻$\ t - 1\ $での状態を$\ S_{t - 1}\ $とすると、$\ S_{t} = G * S_{t - 1}\ $と表すことができる。
よって、$\ G\ $の逆行列が存在するならば、明らかに$\ S_{-T} = (G^{-1})^T * S_{0}\ $が成り立つので、これを計算するだけでよい。
存在しない場合は、解の存在性を見ればよい。すなわち、$\ G^T * S_{-T} = S_{0}\ $という方程式を満たす解$\ S_{-T}\ $が存在するかどうかを判定できればよい。線形代数の教科書を取り出して復習してみると、$\ Ax = b\ $の解が存在するための必要十分条件が$\ rank([A : b]) = rank(A)\ $が成り立つことであるとわかるため、そのように判定する。解が存在すればambiguous
、存在しないならばnone
である。
ただし、行列の中身は常に$\ mod\ 2\ $で見ておき、小数が現れないようにすることができる。
実装
#include "bits/stdc++.h" using namespace std; typedef int Type; typedef vector<vector<Type>> Matrix; int GetRank(Matrix a) { int h = a.size(), w = a[0].size(); int res = 0, now = 0; for (int i = 0; i < h; i ++) { Type ma = 0.0; int pivot; for (int j = i; j < h; j ++) { if (a[j][now] > ma) { ma = a[j][now]; pivot = j; } } if (ma == 0.0) { now ++; if (now == w) break; i --; continue; } if (pivot != i) { for (int j = 0; j < w; j ++) { swap(a[i][j], a[pivot][j]); } } Type tmp = 1.0 / a[i][now]; for (int j = 0; j < w; j ++) a[i][j] *= tmp; for (int j = 0; j < h; j ++) { if (i != j) { Type tmp2 = a[j][now]; for (int k = 0; k < w; k ++) { a[j][k] = ((a[j][k] - a[i][k] * tmp2) + 2) % 2; } } } res ++; } return res; } bool Inv(Matrix a, Matrix &inv) { //square int n = a.size(); for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { inv[i][j] = (i == j ? 1.0 : 0.0); } } for (int i = 0; i < n; i ++) { Type ma = 0.0; int pivot; for (int j = i; j < n; j ++) { if (a[j][i] > ma) { ma = a[j][i]; pivot = j; } } if (ma == 0.0) return false; //no inverse matrix if (pivot != i) { for (int j = 0; j < n; j ++) { swap(a[i][j], a[pivot][j]); swap(inv[i][j], inv[pivot][j]); } } Type tmp = 1.0 / a[i][i]; for (int j = 0; j < n; j ++) { a[i][j] *= tmp; inv[i][j] *= tmp; } for (int j = 0; j < n; j ++) { if (i != j) { Type tmp2 = a[j][i]; for (int k = 0; k < n; k ++) { a[j][k] = ((a[j][k] - a[i][k] * tmp2) + 2 ) % 2; inv[j][k] = ((inv[j][k] - inv[i][k] * tmp2) + 2) % 2; } } } } return true; } Matrix Mul(const Matrix &a, const Matrix &b) { Matrix c(a.size(), vector<Type> (b[0].size())); for (int i = 0; i < a.size(); i ++) { for (int k = 0; k < b.size(); k ++) { for (int j = 0; j < b[0].size(); j ++) { c[i][j] = ((c[i][j] + a[i][k] * b[k][j])) % 2; } } } return c; } Matrix Pow(Matrix a, long long n) { //a^n, square Matrix b(a.size(), vector<Type> (a.size())); for (int i = 0; i < a.size(); i ++) { b[i][i] = 1; } while (n > 0) { if (n & 1) b = Mul(b, a); a = Mul(a, a); n >>= 1; } return b; } void PrintMatrix(const Matrix &a) { int h = a.size(), w = a[0].size(); for (int i = 0; i < h; i ++) { for (int j = 0; j < w; j ++) { cout << a[i][j] << ' '; } cout << endl; } } int main() { int n; scanf("%d", &n); Matrix g(n, vector<int> (n)); for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { scanf("%d", &g[i][j]); } } Matrix v(n, vector<int> (1)); for (int i = 0; i < n; i ++) scanf("%d", &v[i][0]); long long t; scanf("%lld", &t); Matrix inv(n, vector<int> (n)); if (Inv(g, inv)) { inv = Pow(inv, t); auto ans = Mul(inv, v); for (int i = 0; i < n; i ++) cout << ans[i][0] << (i == n - 1 ? '\n' : ' '); } else { auto g_t = Pow(g, t); Matrix g_tv(n, vector<int> (n + 1)); for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { g_tv[i][j] = g_t[i][j]; } } for (int i = 0; i < n; i ++) g_tv[i][n] = v[i][0]; if (GetRank(g_tv) == GetRank(g_t)) { cout << "ambiguous" << endl; } else { cout << "none" << endl; } } return 0; }