#1149005 (C++17) No.557 点対称

• 問題: No.557 点対称
• ユーザー: vjudge1
• 提出日時: 2026-02-21 22:32:16
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 2,733 bytes
• コンパイル時間: 2,167 ms
• コンパイル使用メモリ: 226,044 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-02-21 22:32:20
• 合計ジャッジ時間: 3,440 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 12 WA * 18

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define int long long

const unsigned int MOD = 1e9 + 7;

int n;
int dp[114514];


template <typename _Tp> class Matrix
{
    size_t n, m;
    _Tp MOD;

  public:
    inline size_t r()
    {
        return n;
    };
    inline size_t c()
    {
        return m;
    };
    const inline size_t r() const
    {
        return n;
    };
    const inline size_t c() const
    {
        return m;
    };

    vector<vector<_Tp>> a;
    Matrix(size_t r, size_t c) : n(r), m(c)
    {
        MOD = numeric_limits<_Tp>::max();
        a = vector<vector<_Tp>>(n, vector<_Tp>(m));
    }
    Matrix(size_t r, size_t c, _Tp x) : n(r), m(c), MOD(x)
    {
        a = vector<vector<_Tp>>(n, vector<_Tp>(m));
    }
    Matrix(vector<vector<_Tp>> A) : a(A), n(A.size()), m(A[0].size())
    {
        n = A.size(), m = A[0].size();
        MOD = numeric_limits<_Tp>::max();
    }
    Matrix(vector<vector<_Tp>> A, _Tp x) : a(A), MOD(x)
    {
        n = A.size(), m = A[0].size();
    }

    const vector<_Tp> &operator[](size_t i) const
    {
        return a[i];
    }

    vector<_Tp> &operator[](size_t i)
    {
        return a[i];
    }

    Matrix operator*(const Matrix &b) const
    {
        if (m != b.r())
        {
            return Matrix<_Tp>(0, 0, MOD);
        }
        Matrix<_Tp> c(n, b.m, MOD);
        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = 0; j < b.c(); ++j)
            {
                for (size_t k = 0; k < m; ++k)
                {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
                }
            }
        }
        return c;
    }

    Matrix operator^(long long k)
    {
        Matrix<_Tp> ret(n, n, MOD);
        for (size_t i = 0; i < n; ++i)
        {
            ret[i][i] = 1;
        }
        for (Matrix<_Tp> A = *this; k; A = A * A, k >>= 1)
        {
            if (k & 1)
                ret = ret * A;
        }
        return ret;
    }
};

int solve_small()
{
    if (n == 1)
    {
        return 2;
    }
    if (n == 2)
    {
        return 4;
    }
    dp[1] = 3;
    dp[2] = 5;
    for (int i = 3; i <= n; ++i)
    {
        dp[i] = dp[i - 2] * 5 % MOD;
    }

    return dp[n - 2] * 4 % MOD;
}

int solve()
{
    if (n == 1)
    {
        return 2;
    }
    if (n == 2)
    {
        return 4;
    }
    Matrix<int> A({{0, 0, 5}, {1, 0, 0}, {0, 1, 0}}, MOD), b({{5, 3, 0}}, MOD); //dp[i], dp[i - 1], dp[i - 2]
    Matrix<int> res = b * (A ^ (n - 2));
    return res[0][0] * 4 % MOD;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    if (n <= 100000)
    {
        cout << solve_small();
        return 0;
    }
    cout << solve();
}