Algoogle

Algorithm for Programming Contest

LiveArchive 4332 Blocks for kids

Category: LiveArchive Tag: matrix

Blocks for kids

問題概要


4種類のピースがあって,高さ2で横がいくらかのパネルをそのピースを回転させずに使って埋める.
横がn(<=1,000,000,000)のパネルが渡された時,2人に分割して渡して敷き詰めさせるときの敷き詰め方の場合の数を求めよ.

解法


長さxのパネルの埋め方

長さxのパネルを2人に分けて埋めるときの場合の数

これで遷移行列を作って行列累乗すればよい

コード


(4332.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
#include <bits/stdc++.h>
using namespace std;

const int mod = 10007;

typedef vector<int> arr;
typedef vector<arr> mat;

mat identity(int n)
{
        mat ret(n,arr(n,0));
        for (int i = 0; i < n; i++) ret[i][i] = 1;
        return ret;
}

arr mul(const mat &A, const arr &x)
{
        arr y(A.size());
        for(int i = 0; i < (int)A.size(); ++i)
                for(int j = 0; j < (int)A[0].size(); ++j)
                        y[i] = (y[i]+A[i][j]*x[j])%mod;
        return y;
}

mat mul(const mat &A, const mat &B)
{
        mat C(A.size(), arr(B[0].size()));
        for(int i = 0; i < (int)C.size(); ++i)
                for(int j = 0; j < (int)C[i].size(); ++j)
                        for(int k = 0; k < (int)A[i].size(); ++k)
                                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%mod;
        return C;
}

mat pow(mat A, int e)
{
        mat ret = identity(A.size());
        for (; e > 0; A=mul(A,A), e>>=1) if(e&1) ret = mul(ret, A);
        return ret;
}

int solve(int x)
{
        if(!x) return 1;
        mat A(4,arr(4));
        A[0][0] = A[0][1] = A[0][2] = A[0][3] = 2;
        A[1][0] = 1;
        A[2][2] = A[2][3] = 2;
        A[3][2] = 1;
        A = pow(A,x-1);
        arr B(4);
        B[0] = 4; B[1] = 1; B[2] = 2; B[3] = 1;
        B = mul(A,B);
        return B[0];
}

int main()
{
        int x;
        while(cin >> x, ~x) cout << solve(x) << endl;
        return 0;
}

Comments