Algoogle

Algorithm for Programming Contest

AOJ 2115 Life Game

Category: AOJ Tag: matrix

Life Game

問題概要


解法


六角格子座標を の大きさの1行で表現する.
あとは遷移行列を書いて累乗していく.

コード


(2115.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <algorithm>
#include <iostream>

#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;
typedef ll number;
typedef number* array;
typedef array* matrix;

int mod;

matrix new_matrix(int n, int m){
    matrix A = new array[n];
    for(int i = 0; i < n; i++){
        A[i] = new number[m];
        for(int j = 0; j < m; j++) A[i][j] = 0;
    }
    return A;
}

matrix identity(int n){
    matrix A = new_matrix(n,n);
    for(int i = 0; i < n; i++) A[i][i] = 1;
    return A;
}
matrix mul_matrix(matrix A, matrix B, int p, int n, int q){
    matrix C = new_matrix(p,q);
    for(int i = 0; i < p; i++){
        for(int j = 0; j < q; j++){
            C[i][j] = 0;
            for(int k = 0; k < n; k++){
                C[i][j] += A[i][k]*B[k][j];
                C[i][j] %= mod;
            }
        }
    }
    return C;
}

matrix pow_matrix(matrix A, int n, int e){
    return e==0? identity(n):
        e%2==0? pow_matrix(mul_matrix(A,A,n,n,n),n,e/2):
        mul_matrix(A,pow_matrix(A,n,e-1),n,n,n);
}

int n, l;
const int dx[] = {-1,0,-1,0,1,0,1};
const int dy[] = {-1,-1,0,0,0,1,1};

bool inrange(int x, int y){
    if(y<n) return (y>=0 && y<2*n-1 && x>=0 && x<n+y);
    return (y>=0 && y<2*n-1 && x>=y-n+1 && x<2*n-1);
}

int main(){
    int cas = 1;
    while(cin >> n >> mod >> l, n || mod || l){
        int N = 2*n - 1;
        matrix col = new_matrix(N*N,1);
        rep(y,N){
            if(y<n) rep(x,n+y) cin >> col[y*N+x][0];
            else repi(x,y-n+1,N) cin >> col[y*N+x][0];
        }
        matrix seq = new_matrix(N*N,N*N);
        rep(y,N){
            if(y<n){
                rep(x,n+y) rep(k,7){
                    if(inrange(x+dx[k],y+dy[k])) seq[y*N+x][(y+dy[k])*N+x+dx[k]] = 1;
                }
            }else{
                repi(x,y-n+1,N) rep(k,7){
                    if(inrange(x+dx[k],y+dy[k])) seq[y*N+x][(y+dy[k])*N+x+dx[k]] = 1;
                }
            }
        }
        matrix ans = mul_matrix(pow_matrix(seq,N*N,l),col,N*N,N*N,1);
        ll cnt = 0;
        rep(i,N*N) cnt += ans[i][0];
        cout << "Case " << cas++ << ": " << cnt << endl;
    }
    return 0;
}

Comments