結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
ユーザー PachicobuePachicobue
提出日時 2017-12-21 23:44:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 3,000 ms
コード長 4,368 bytes
コンパイル時間 2,213 ms
コンパイル使用メモリ 198,084 KB
最終ジャッジ日時 2025-01-05 06:09:37
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

template <typename T, std::size_t n>
ostream& operator<<(ostream& os, const array<T, n>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

constexpr int N = 31;

struct Vec {
    Vec()
    {
        for (int i = 0; i < N; i++) {
            table[i] = 0;
        }
    }

    Vec(const string& s)
    {
        assert(s.size() == N);
        for (int i = 0; i < N; i++) {
            table[i] = s[i] - '0';
        }
    }
    ll operator*(const Vec& vec) const
    {
        ll ans = 0;
        for (int i = 0; i < N; i++) {
            ans += table[i] * vec.table[i];
            ans %= MOD;
        }
        return ans;
    }

    array<ll, N> table;
};

struct Matrix {
    Matrix()
    {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                table[i][j] = 0;
            }
        }
    }

    Matrix(const array<string, N>& s)
    {
        for (int i = 0; i < N; i++) {
            assert(s[i].size() == N);
            for (int j = 0; j < N; j++) {
                table[i][j] = s[i][j] - '0';
            }
        }
    }

    static Matrix Unit()
    {
        Matrix ans;
        for (int i = 0; i < N; i++) {
            ans.table[i][i] = 1;
        }
        return ans;
    }

    Matrix operator*(const Matrix& mat) const
    {
        Matrix ans;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    ans.table[i][j] += table[i][k] * mat.table[k][j];
                    ans.table[i][j] %= MOD;
                }
            }
        }
        return ans;
    }

    array<array<ll, N>, N> table;
};

inline Vec operator*(const Vec& vec, const Matrix& mat)
{
    Vec ans;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans.table[i] += mat.table[j][i] * vec.table[j];
            ans.table[i] %= MOD;
        }
    }
    return ans;
}

Matrix power(const Matrix& mat, const ll n)
{
    if (n == 0) {
        return Matrix::Unit();
    }
    if (n % 2 == 1) {
        return mat * power(mat, n - 1);
    } else {
        const Matrix pp = power(mat, n / 2);
        return pp * pp;
    }
}

int main()
{

    cin.tie(0);
    ios::sync_with_stdio(false);

    const array<string, N> trans{{
        //0123456789012345678901234567890
        "0000000000000000000010000000001",
        "0000000010000010000000000100001",
        "0000000000000000000010000100001",
        "0000000000000010000010000000001",
        "0000000010000010000010000100001",
        "0000000000000000001000000010100",
        "0000000001000000000000000010000",
        "0000000001000000001000000010100",
        "0000000000000000000001000000000",
        "0000000000000000010001000000100",
        "0000010000000000000001000001000",
        "1000010000001000010001100001010",
        "0000000000000000000100000000001",
        "0010000000000010000100001000001",
        "0000000000000000000100000000001",
        "0010000000000010000100001000001",
        "0010000000000010000100001000001",
        "0000001000000000100000000000100",
        "0000000000100000100000000000000",
        "0000001000100000100000000000100",
        "0000000000010000000000000000000",
        "0100000000010100000000010000000",
        "0000000100000000000000000000001",
        "0001000100000001000000000100001",
        "0001000100000001000000000100001",
        "0000000100000000000000000000001",
        "0001000100000001000000000100001",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
        "0000100000000000100000000010000",
    }};
    //0123456789012345678901234567890
    const string init = "0011000110000021000110001200003";
    const string proper = "0000000000010101100001011011111";

    const Matrix mat(trans);
    const Vec initial(init);
    const Vec last(proper);
    ll n;
    cin >> n;
    if (n == 1) {
        cout << 2 << endl;
    } else {
        const Vec ans = initial * power(mat, n - 2);
        show(ans.table);
        cout << ans * last << endl;
    }

    return 0;
}
0