結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
コンテスト
ユーザー Pachicobue
提出日時 2017-12-21 23:44:58
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 12 ms / 3,000 ms
+ 923µs
コード長 4,368 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,230 ms
コンパイル使用メモリ 218,856 KB
実行使用メモリ 9,916 KB
最終ジャッジ日時 2026-10-10 18:15:27
合計ジャッジ時間 4,631 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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