読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
}