AOJ 2115 : Life Game
問題リンク : Life Game | Aizu Online Judge
問題概要:
六角のセルにウィルスが存在する
1ターン毎にウィルスが存在するセルに隣接する全てのセルに今いるセルに存在するウィルスの数と同じ数のウィルスが発生する
1つのセルにM以上のウィルスが存在する場合はMでmodをとった数までウィルスが減る
Lターン後に存在するウィルスの数を求めよ
解法:
行列におとして行列のべき乗計算をした
それぞれのセルについて、そのセル自身またはそのセルに隣接するセルには1を、その他は0を要素とするような正方行列をつくる
この行列をAとする
セルの初期状態の行列をb0とする
iターン後のセルの状態をbi(0<=i<=L)とする
この時、
A*b0 = b1
A*b1 = b2 -> A*A*b0 = b2 -> A~2*b0 = b2
A*b2 = b3 -> A*A*A*b0 = b3 -> A~3*b0 = b3
...
この様に
Aのn乗に初期状態b0をかけた行列の要素の総和が答えとなる
コード:
#define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define MAX 1000 using namespace std; typedef long long ll; typedef vector<ll> VI; typedef vector<VI> VVI; typedef VVI matrix; const int diff = 100; int dx[] = { 0,1,1,0,-1,-1}; int dy[] = {-1,0,1,1, 0,-1}; int N,L,min_x,min_y,max_x,max_y; int Index[MAX][MAX]; ll M; //行列計算 int main() { int CNT = 1; while(cin >> N >> M >> L,N|M|L) { min_x = min_y = 999; max_x = max_y = 0; rep(i,MAX)rep(j,MAX)Index[i][j] = inf; int x = diff; int y = diff; int add = 0; int size = 0; vector<ll> b; rep(i,2*N-1) { int nx = x,ny = y; rep(j,N+add) { int value; cin >> value; b.push_back(value); Index[ny][nx] = size; size++; nx += dx[1]; ny += dy[1]; } if(i < N-1)add++; else add--; if(i < N-1) { x += dx[3], y += dy[3]; } else { x += dx[2], y += dy[2]; } } matrix A = identity(size); REP(i,diff,diff+2*N) { REP(j,diff,diff+2*N) { if(Index[i][j] == inf)continue; int cur = Index[i][j]; rep(k,6) { int nx = j + dx[k]; int ny = i + dy[k]; if(Index[ny][nx] == inf)continue; int next = Index[ny][nx]; A[cur][next] = 1; } } } A = pow(A,L); vector<ll> c = multi(A,b); ll ans = 0; rep(i,c.size())ans += c[i]%M; cout << "Case " << CNT++ << ": " << ans << endl; } return 0; }