#1111834 (C++23) No.3227 Matrix Query

• 問題: No.3227 Matrix Query
• ユーザー: nonon
• 提出日時: 2025-08-12 15:06:10
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,524 ms / 8,000 ms
• コード長: 11,050 bytes
• コンパイル時間: 4,515 ms
• コンパイル使用メモリ: 292,872 KB
• 実行使用メモリ: 9,600 KB
• 最終ジャッジ日時: 2025-08-12 15:06:43
• 合計ジャッジ時間: 31,497 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

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

using ll = long long;

bool chmin(auto &a, auto b) { return a > b ? a = b, true : false; }
bool chmax(auto &a, auto b) { return a < b ? a = b, true : false; }

struct modint {
    modint() : x(0) {}
    modint(long long v) {
        long long y = v % m();
        if (y < 0) y += m();
        x = (unsigned int)(y);
    }
    static void set_mod(int _m) { MOD = _m; }
    static modint raw(int v) {
        modint a;
        a.x = v;
        return a;
    }
    static int mod() { return m(); }
    unsigned int val() const { return x; }
    modint& operator++() {
        x++;
        if (x == m()) x = 0;
        return *this;
    }
    modint& operator--() {
        if (x == 0) x = m();
        x--;
        return *this;
    }
    modint operator++(int) {
        modint res = *this;
        ++*this;
        return res;
    }
    modint operator--(int) {
        modint res = *this;
        --*this;
        return res;
    }
    modint& operator+=(const modint &r) {
        x += r.x;
        if (x >= m()) x -= m();
        return *this;
    }
    modint& operator-=(const modint &r) {
        x -= r.x;
        if (x >= m()) x += m();
        return *this;
    }
    modint& operator*=(const modint &r) {
        unsigned long long y = x;
        y *= r.x;
        x = (unsigned int)(y % m());
        return *this;
    }
    modint &operator/=(const modint &r) {
        return *this = *this * r.inv();
    }
    friend modint operator+(const modint &a, const modint &b) {
        return modint(a) += b;
    }
    friend modint operator-(const modint &a, const modint &b) {
        return modint(a) -= b;
    }
    friend modint operator*(const modint &a, const modint &b) {
        return modint(a) *= b;
    }
    friend modint operator/(const modint &a, const modint &b) {
        return modint(a) /= b;
    }
    friend bool operator==(const modint &a, const modint &b) {
        return a.x == b.x;
    }
    friend bool operator!=(const modint &a, const modint &b) {
        return a.x != b.x;
    }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long k) const {
        assert(k >= 0);
        modint a = *this;
        modint res = 1;
        while (k > 0) {
            if (k & 1) res *= a;
            a *= a;
            k >>= 1;
        }
        return res;
    }
    modint inv() const {
        long long a = x, b = m(), u = 1, v = 0;
        while (b > 0) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return modint(u);
    }
private:
    unsigned int x;
    static unsigned int MOD;
    static unsigned int m() { return MOD; }
};
unsigned int modint::MOD = -1;

template<typename mint>
struct matrix : vector<vector<mint>> {
    using vector<vector<mint>>::vector;
    matrix(int h, int w) : vector<vector<mint>>(h, vector<mint>(w)) {}
    matrix &operator*=(const mint &r) {
        for (vector<mint> &v : *this) {
            for (mint &a : v) a *= r;
        }
        return *this;
    }
    matrix &operator/=(const mint &r) {
        mint invr = r.inv();
        return *this *= invr;
    }
    matrix &operator+=(const matrix& a) {
        assert(this->size() == a.size());
        for (int i = 0; i < int(this->size()); i++) {
            assert((*this)[i].size() == a[i].size());
            for (int j = 0; j < int((*this)[i].size()); j++) {
                (*this)[i][j] += a[i][j];
            }
        }
        return *this;
    }
    matrix &operator-=(const matrix& a) {
        assert(this->size() == a.size());
        for (int i = 0; i < int(this->size()); i++) {
            assert((*this)[i].size() == a[i].size());
            for (int j = 0; j < int((*this)[i].size()); j++) {
                (*this)[i][j] -= a[i][j];
            }
        }
        return *this;
    }
    matrix &operator*=(const matrix &a) {
        int n = this->size(), m = a.size();
        assert(m >= 1);
        int l = a[0].size();
        matrix res(n, vector<mint>(l));
        for (int i = 0; i < n; i++) {
            assert(int((*this)[i].size()) == m);
            for (int k = 0; k < m; k++) {
                for (int j = 0; j < l; j++) {
                    res[i][j] += (*this)[i][k] * a[k][j];
                }
            }
        }
        return *this = res;
    }
    matrix operator*(const mint &r) const { return matrix(*this) *= r; }
    matrix operator/(const mint &r) const { return matrix(*this) /= r; }
    matrix operator+(const matrix &a) const { return matrix(*this) += a; }
    matrix operator-(const matrix &a) const { return matrix(*this) -= a; }
    matrix operator*(const matrix &a) const { return matrix(*this) *= a; }
    static constexpr matrix I(int n) {
        matrix res(n, n);
        for (int i = 0; i < n; i++) {
            res[i][i] = 1;
        }
        return res;
    }
    static constexpr matrix O(int n) { return matrix(n, n); }
    matrix pow(long long k) const {
        matrix res = I(this->size()), a = *this;
        while (k > 0) {
            if (k & 1) res *= a;
            a *= a;
            k >>= 1;
        }
        return res;
    }
    mint det() const {
        int n = this->size();
        assert(n >= 1);
        assert((*this)[0].size() == this->size());
        mint res = 1;
        matrix a = *this;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (a[j][i] != 0) {
                    if (i != j) res = -res;
                    swap(a[i], a[j]);
                    break;
                }
            }
            if (a[i][i] != 0) {
                for (int j = i + 1; j < n; j++) {
                    mint inv = a[j][i] * a[i][i].inv();
                    for (int k = i + 1; k < n; k++) {
                        a[j][k] -= a[i][k] * inv;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            res *= a[i][i];
        }
        return res;
    }
    matrix inv() const {
        int n = this->size();
        matrix a = *this, res = I(n);
        for (int i = 0; i < n; i++) {
            if (a[i][i] == 0) {
                for (int j = i + 1; j < n; j++) {
                    if (a[j][i] != 0) {
                        swap(a[i], a[j]);
                        swap(res[i], res[j]);
                        break;
                    }
                }
            }
            assert(a[i][i] != 0);
            mint cef = a[i][i].inv();
            for (int j = 0; j < n; j++) {
                a[i][j] *= cef;
                res[i][j] *= cef;
            }
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    cef = a[j][i];
                    for (int k = 0; k < n; k++) {
                        a[j][k] -= a[i][k] * cef;
                        res[j][k] -= res[i][k] * cef;
                    }
                }
            }
        }
        return res;
    }
};

template <typename Monoid>
struct segtree {
    using M = Monoid;
    using S = typename M::S;
    segtree() : segtree(0) {}
    segtree(int _n) : segtree(vector<S>(_n, M::e())) {}
    segtree(const vector<S> &v) : n(v.size()) {
        log = 1;
        while ((1 << log) < n) log++;
        sz = 1 << log;
        d = vector<S>(2 * sz, M::e());
        for (int i = 0; i < n; i++) d[i + sz] = v[i];
        for (int i = sz - 1; i >= 1; i--) update(i);
    }
    void set(int p, const S &x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + sz];
    }
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        l += sz;
        r += sz;
        S pl = M::e(), pr = M::e();
        while (l < r) {
            if (l & 1) pl = M::op(pl, d[l++]);
            if (r & 1) pr = M::op(d[--r], pr);
            l >>= 1;
            r >>= 1;
        }
        return M::op(pl, pr);
    }
    S all_prod() const { return d[1]; }
    template<typename C>
    int max_right(int l, const C &check) const {
        assert(0 <= l && l <= n);
        assert(check(M::e()));
        if (l == n) return l;
        l += sz;
        S p = M::e();
        do {
            while (!(l & 1)) l >>= 1;
            S np = M::op(p, d[l]);
            if (!check(np)) {
                while (l < sz) {
                    l <<= 1;
                    np = M::op(p, d[l]);
                    if (check(np)) {
                        p = np;
                        l++;
                    }
                }
                return l - sz;
            }
            p = np;
            l++;
        } while ((l & -l) != l);
        return n;
    }
    template<typename C>
    int max_right(const C &check) const {
        return max_right(0, check);
    }
    template<typename C>
    int min_left(int r, const C &check) const {
        assert(0 <= r && r <= n);
        assert(check(M::e()));
        if (r == 0) return r;
        r += sz;
        S p = M::e();
        do {
            r--;
            while (r > 1 && r & 1) r >>= 1;
            S np = M::op(d[r], p);
            if (!check(np)) {
                while (r < sz) {
                    (r <<= 1)++;
                    np = M::op(d[r], p);
                    if (check(np)) {
                        p = np;
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            p = np;
        } while ((r & -r) != r);
        return 0;
    }
    template<typename C>
    int min_left(const C &check) const {
        return min_left(n, check);
    }
private:
    int n, log, sz;
    vector<S> d;
    void update(int p) {
        d[p] = M::op(d[2 * p], d[2 * p + 1]);
    }
};

using mint = modint;
using Mat = matrix<mint>;

struct Monoid {
    using S = Mat;
    static S op(const S &a, const S &b) {
        return a * b;
    }
    static S e() {
        return Mat::I(2);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int P, N;
    cin >> P >> N;
    mint::set_mod(P);
    segtree<Monoid> seg(N);
    for (int i = 0; i < N; i++) {
        Mat A(2, 2);
        for (int s : {0, 1}) {
            for (int t : {0, 1}) {
                int a;
                cin >> a;
                A[s][t] = a;
            }
        }
        seg.set(i, A);
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int p, L, R;
        cin >> p >> L >> R;
        p--, L--;
        Mat A(2, 2);
        for (int s : {0, 1}) {
            for (int t : {0, 1}) {
                int a;
                cin >> a;
                A[s][t] = a;
            }
        }
        seg.set(p, A);
        A = seg.prod(L, R);
        for (int s : {0, 1}) {
            for (int t : {0, 1}) {
                cout << A[s][t].val() << " \n"[t];
            }
        }
    }
}