#1111225 (C++23) No.3226 2×2行列累乗

提出ソース
結果

問題	No.3226 2×2行列累乗
コンテスト
ユーザー	こめだわら
提出日時	2025-08-08 22:37:48
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	8,741 bytes
コンパイル時間	4,920 ms
コンパイル使用メモリ	335,828 KB
実行使用メモリ	7,716 KB
最終ジャッジ日時	2025-08-08 22:37:55
合計ジャッジ時間	6,258 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 27
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }


namespace noya2 {

template<typename T, size_t hw = -1uz>
struct matrix {
    static constexpr int h = hw, w = hw;
    std::array<T, hw*hw> m;
    matrix () : m({}) {}
    matrix (const std::array<T, hw*hw> &_m) : m(_m) {}
    matrix (const std::array<std::array<T, hw>, hw> &_m){
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    matrix (const std::vector<std::vector<T>> &_m){
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    auto operator[](int i) const {
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    auto operator[](int i){
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    matrix &operator+= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] += r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator-= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] -= r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator*= (const matrix &r){
        matrix ret;
        for (int i = 0; i < h; i++){
            for (int k = 0; k < w; k++){
                for (int j = 0; j < r.w; j++){
                    ret.m[idx(i,j)] += m[idx(i,k)] * r.m[idx(k,j)];
                }
            }
        }
        return *this = ret;
    }
    matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
    matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
    matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
    matrix& operator*=(const T &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] *= r;
            }
        }
        return *this;
    }
    friend matrix operator* (const T &r, const matrix &mat){
        return matrix(mat) *= r;
    }
    friend matrix operator* (const matrix &mat, const T &r){
        return matrix(mat) *= r;
    }
    matrix pow(long long n){
        if (n == 0) return e();
        matrix f = pow(n / 2);
        matrix ret = f * f;
        if (n & 1) ret *= (*this);
        return ret;
    }
    int idx(int i, int j){
        return i * w + j;
    }
    static matrix e(){
        matrix ret;
        for (int i = 0; i < h; i++){
            ret[i][i] = T(1);
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
        for (int i = 0; i < mat.h; i++){
            if (i != 0) os << '\n';
            for (int j = 0; j < mat.w; j++){
                if (j != 0) os << ' ';
                os << mat[i][j];
            }
        }
        return os;
    }
    friend std::istream &operator>>(std::istream &is, matrix &mat){
        for (int i = 0; i < mat.h; i++){
            for (int j = 0; j < mat.w; j++){
                is >> mat[i][j];
            }
        }
        return is;
    }
    friend bool operator==(const matrix &a, const matrix &b){
        for (int i = 0; i < a.h; i++){
            for (int j = 0; j < a.w; j++){
                if (a[i][j] != b[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
};

template<typename T>
struct matrix<T,-1uz> {
    int h, w;
    std::vector<T> m;
    matrix () {}
    matrix (int _h) : matrix(_h,_h) {}
    matrix (int _h, int _w) : h(_h), w(_w), m(_h*_w) {}
    matrix (int _h, int _w, const std::vector<T> &_m) : h(_h), w(_w), m(_m) {
        assert((int)_m.size() == _h*_w);
    }
    matrix (const std::vector<std::vector<T>> &_m){
        h = _m.size();
        assert(h >= 1);
        w = _m[0].size();
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
            m[idx(i,j)] = _m[i][j];
        }
    }
    auto operator[](int i) const {
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    auto operator[](int i){
        return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
    }
    matrix &operator+= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] += r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator-= (const matrix &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] -= r.m[idx(i,j)];
            }
        }
        return *this;
    }
    matrix &operator*= (const matrix &r){
        matrix ret(h, r.w);
        for (int i = 0; i < h; i++){
            for (int k = 0; k < w; k++){
                for (int j = 0; j < r.w; j++){
                    ret.m[i*r.w+j] += m[idx(i,k)] * r.m[k*r.w+j];
                }
            }
        }
        return *this = ret;
    }
    matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
    matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
    matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
    matrix& operator*=(const T &r){
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                m[idx(i,j)] *= r;
            }
        }
        return *this;
    }
    friend matrix operator* (const T &r, const matrix &mat){
        return matrix(mat) *= r;
    }
    friend matrix operator* (const matrix &mat, const T &r){
        return matrix(mat) *= r;
    }
    matrix pow(long long n){
        if (n == 0) return e(h);
        matrix f = pow(n / 2);
        matrix ret = f * f;
        if (n & 1) ret *= (*this);
        return ret;
    }
    int idx(int i, int j){
        return i * w + j;
    }
    static matrix e(int _h){
        auto ret = matrix(_h, _h);
        for (int i = 0; i < _h; i++){
            ret[i][i] = T(1);
        }
        return ret;
    }
    friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
        for (int i = 0; i < mat.h; i++){
            if (i != 0) os << '\n';
            for (int j = 0; j < mat.w; j++){
                if (j != 0) os << ' ';
                os << mat[i][j];
            }
        }
        return os;
    }
    friend std::istream &operator>>(std::istream &is, matrix &mat){
        for (int i = 0; i < mat.h; i++){
            for (int j = 0; j < mat.w; j++){
                is >> mat[i][j];
            }
        }
        return is;
    }
};

template<typename T, size_t _hw = -1uz>
T determinant(matrix<T, _hw> mat){
    int hw = mat.h;
    T ret = 1;
    for (int i = 0; i < hw; i++) {
        int idx = -1;
        for (int j = i; j < hw; j++) {
            if (mat[j][i] != 0) {
                idx = j;
                break;
            }
        }
        if (idx == -1) return 0;
        if (i != idx) {
            ret *= T(-1);
            for (int j = 0; j < hw; j++){
                std::swap(mat[i][j],mat[idx][j]);
            }
        }
        ret *= mat[i][i];
        T inv = T(1) / mat[i][i];
        for (int j = 0; j < hw; j++) {
            mat[i][j] *= inv;
        }
        for (int j = i + 1; j < hw; j++) {
            T a = mat[j][i];
            if (a == 0) continue;
            for (int k = i; k < hw; k++) {
                mat[j][k] -= mat[i][k] * a;
            }
        }
    }
    return ret;
}

} // namespace noya2
using namespace noya2;


#include <atcoder/all>
using namespace atcoder;
using mint = modint;

void solve() {
    ll A,B,C,D,S,T,N,K;
    cin>>A>>B>>C>>D>>S>>T>>N>>K;
    mint::set_mod(K);
    matrix<mint> M(2,2,{A,B,C,D});
    matrix<mint> p(2,1,{S,T});
    matrix<mint> mp=M.pow(N);
    matrix<mint> ans=mp*p;
    rep(i,2){
        cout<<ans[i][0].val()<<' ';
    }
    cout<<endl;
    return;
}


int main() {
    ll T=1;
    while (T--){
        solve();
    }
    return 0;
}
yukicoder

結果

ソースコード
