#816437 (C++17) No.1136 Four Points Tour

• 問題: No.1136 Four Points Tour
• ユーザー: Slephy
• 提出日時: 2022-11-16 11:28:29
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 10,035 bytes
• コンパイル時間: 4,446 ms
• コンパイル使用メモリ: 269,344 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-17 08:35:59
• 合計ジャッジ時間: 5,770 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
01_Sample03_evil.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil1.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil2.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil3.txt	AC	3 ms; 5,376 KB
04_Rnd_large_evil4.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil5.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil6.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil7.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil8.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil9.txt	AC	2 ms; 5,376 KB
04_Rnd_large_evil10.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil1.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil2.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil3.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil4.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil5.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil6.txt	AC	2 ms; 5,376 KB
05_Rnd_huge_evil7.txt	AC	2 ms; 5,376 KB
99_evil_01.txt	AC	2 ms; 5,376 KB

ソースコード

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
    using mint = modint1000000007;
    // using mint = modint998244353;
    // using mint = modint;
    // const int MOD = mint::mod();
#endif
#ifdef LOCAL_DEBUG
    #define cout cout<<' '
#endif
using ll = long long;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
// constexpr int MOD = (int)1e9 + 7;
// constexpr int MOD = (int)998244353;
constexpr int INF = (int)1e9 + 1001010;
constexpr ll llINF = (ll)4e18 + 11000010;
constexpr double PI = 3.14159265358979;
constexpr double EPS = 1e-10;
#define Isize(x) (int)(size(x))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end());
#define endn "\n"
#define SUM(v) accumulate(ALL(v), 0LL)
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

template <class T> inline vector<vector<T>> vector2(const size_t &i, const size_t &j, const T &init = T()) {
    return vector<vector<T>>(i, vector<T>(j, init));
}
template <class T> inline vector<vector<vector<T>>> vector3(const size_t &i, const size_t &j, const int &k, const T &init = T()) {
    return vector<vector<vector<T>>>(i, vector<vector<T>>(j, vector<T>(k, init)));
}
template <class T> inline vector<vector<vector<vector<T>>>> vector4(const size_t &i, const size_t &j, const size_t &k, const size_t &l, const T &init = T()) {
    return vector<vector<vector<vector<T>>>>(i, vector<vector<vector<T>>>(j, vector<vector<T>>(k, vector<T>(l, init))));
}

const string VEC_ELEM_SEPARATION = " ";
const string VEC_VEC_SEPARATION = endn;
template<class T> istream & operator >> (istream &i, vector<T> &A) {for(auto &I : A) {i >> I;} return i;}
template<class T> ostream & operator << (ostream &o, const vector<vector<T>> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_VEC_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const vector<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const deque<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T, class U> istream & operator >> (istream &i, pair<T,U> &A) {i >> A.first >> A.second; return i;}
template<class T, class U> ostream & operator << (ostream &o, const pair<T,U> &A) {o << A.first << " " << A.second; return o;}
template<class T, class U, class V> istream & operator >> (istream &i, tuple<T,U,V>&A) {i >> get<0>(A) >> get<1>(A) >> get<2>(A); return i;}
template<class T, class U, class V> ostream & operator << (ostream &o, const tuple<T,U,V> &A) {o << get<0>(A) << " " << get<1>(A) << " " << get<2>(A); return o;}

template<class T> vector<T>& operator ++(vector<T> &A, int n) {for(auto &I : A) {I++;} return A;}
template<class T> vector<T>& operator --(vector<T> &A, int n) {for(auto &I : A) {I--;} return A;}

template<class T, class U> bool chmax(T &a, const U &b){return ((a < b) ? (a = b, true) : false);}
template<class T, class U> bool chmin(T &a, const U &b){return ((a > b) ? (a = b, true) : false);}

ll floor(ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) != (b>0))) ? a/b-1 : a/b);}
ll ceil (ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) == (b>0))) ? a/b+1 : a/b);}
ll gcd(ll a, ll b){return ((b==0) ? a : gcd(b, a%b));}
ll lcm(ll a, ll b){return a / gcd(a,b) * b;}
bool is_in(ll inf, ll n, ll sup){return(inf <= n && n <= sup);}
// ================================== ここまでテンプレ ==================================

template<class T>
class Matrix{
private:
    // // ムーブ代入演算子の禁止
    // Matrix& operator=(Matrix&&) = delete;

public:
    // コンストラクタ
    Matrix(size_t h_, size_t w_, T init = T()) : h(h_), w(w_), mat(vector<vector<T>>(h_, vector<T>(w_, init))) {}
    Matrix(const vector<vector<T>> &mat_) : h(mat_.size()), w(mat[0].size()), mat(mat_) {}
    Matrix(const Matrix<T> &mat_) = default;
    Matrix(Matrix<T> &&mat_) : h(mat_.h), w(mat_.w), mat(move(mat_.mat)) {}

    // ゲッター
    size_t height() const {return h;}
    size_t width() const {return w;}

    // 代入演算子のオーバーロード
    Matrix<T>& operator = (const Matrix<T> &mat_) = default; // copy
    Matrix<T>& operator = (Matrix<T> &&mat_) {               // move
        h = mat_.h; w = mat_.w;
        mat = move(mat_.mat);
        mat_.h = 0; mat_.w = 0;
        return *this;
    }

    // 添え字演算子のオーバーロード
    vector<T>& operator [](int index){
        assert(0 <= index && index < h);
        return mat[index];
    }
    const vector<T> operator [](int index)const{
        assert(0 <= index && index < h);
        return mat[index];
    }

    // イテレータ
    auto begin() {return mat.begin();}
    auto end()   {return mat.end();}

    // 入出力ストリーム
    friend istream & operator >> (istream &i, Matrix<T> &mat) {for(auto &I : mat) for(auto &J : I){i >> J;} return i;}
    friend ostream & operator << (ostream &o, const Matrix &A) {o << A.mat; return o;}

    // 単位行列
    static Matrix<T> identity(unsigned int n){
        Matrix<T> res(n, n, 0);
        for(int i=0; i<n; i++){
            res[i][i] = 1;
        }
        return res;
    }
    static Matrix<T> identity(const Matrix<T> &mat_like){
        assert(mat_like.h == mat_like.w);
        return Matrix<T>::identity(mat_like.h);
    }
    static Matrix<T> zero(unsigned int h){
        return Matrix<T>(h, h, 0);
    }
    static Matrix<T> zero(unsigned int h, unsigned int w){
        return Matrix<T>(h, w, 0);
    }
    static Matrix<T> zero(const Matrix<T> &mat_like){
        return Matrix<T>::zero(mat_like.h, mat_like.w);
    }

    // 算術演算子のオーバーロード
    Matrix<T> operator +(){
        return *this;
    }
    Matrix<T> operator -(){
        Matrix<T> res(h, w);
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                res[i][j] = -mat[i][j];
            }
        }
        return res;
    }
    Matrix<T> operator +(const Matrix<T> &other) const {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                res[i][j] = mat[i][j] + other[i][j];
            }
        }
        return res;
    }
    Matrix<T> operator -(const Matrix<T> &other) const {
        assert(h == other.h && w == other.w);
        Matrix<T> res(h, w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                res[i][j] = mat[i][j] - other[i][j];
            }
        }
        return res;
    }
    Matrix<T> operator *(const Matrix<T> &other) const {
        assert(w == other.h);
        Matrix<T> res(h, other.w);
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < other.w; ++j){
                for (int k = 0; k < w; ++k){
                    res[i][j] += mat[i][k] * other[k][j];
                }
            }
        }
        return res;
    }
    Matrix<T>& operator +=(const Matrix<T> &other){
        *this = *this + other;
        return *this;
    }
    Matrix<T>& operator -=(const Matrix<T> &other){
        *this = *this - other;
        return *this;
    }
    Matrix<T>& operator *=(const Matrix<T> &other){
        *this = *this * other;
        return *this;
    }
    friend Matrix<T>& operator +=(Matrix<T> &mat, const T &val){
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) mat[i][j] += val;
        return mat;
    }
    friend Matrix<T>& operator -=(Matrix<T> &mat, const T &val){
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) mat[i][j] -= val;
        return mat;
    }
    friend Matrix<T>& operator *=(Matrix<T> &mat, const T &val){
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) mat[i][j] *= val;
        return mat;
    }
    friend Matrix<T> operator +(const Matrix<T> &mat, const T &val){
        Matrix<T> res(mat.h, mat.w);
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) res[i][j] = mat[i][j] + val;
        return res;
    }
    friend Matrix<T> operator +(const T &val, const Matrix<T> &mat){
        return mat + val;
    }
    friend Matrix<T> operator -(const Matrix<T> &mat, const T &val){
        Matrix<T> res(mat.h, mat.w);
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) res[i][j] = mat[i][j] - val;
        return res;
    }
    friend Matrix<T> operator -(const T &val, const Matrix<T> &mat){
        Matrix<T> res(mat.h, mat.w);
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) res[i][j] = val - mat[i][j];
        return res;
    }
    friend Matrix<T> operator *(const Matrix<T> &mat, const T &val){
        Matrix<T> res(mat.h, mat.w);
        for(int i = 0; i < mat.h; i++) for(int j = 0; j < mat.w; j++) res[i][j] = mat[i][j] * val;
        return res;
    }
    friend Matrix<T> operator *(const T &val, const Matrix<T> &mat){
        return mat * val;
    }


    // 行列累乗
    Matrix<T> pow(unsigned long long n) const{
        assert(h == w);
        Matrix<T> res = Matrix<T>::identity(h);
        Matrix<T> tmp = *this;
        while(n > 0){
            if(n & 1) res *= tmp;
            tmp *= tmp;
            n >>= 1;
        }
        return res;
    }

// メンバ変数
private:
    vector<vector<T>> mat;
    size_t h, w;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; cin >> n;
    Matrix<mint> mat = vector<vector<mint>>{
        {0, 1, 1, 1},
        {1, 0, 1, 1},
        {1, 1, 0, 1},
        {1, 1, 1, 0},
    };

    Matrix<mint> init(4, 1, 0);
    init[0][0] = 1;

    Matrix<mint> ans = mat.pow(n) * init;
    cout << ans[0][0].val() << endl;
    return 0;
}