結果
| 問題 | No.3227 Matrix Query |
| コンテスト | |
| ユーザー |
 joji
|
| 提出日時 | 2026-01-21 20:00:30 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,129 ms / 8,000 ms |
| コード長 | 12,606 bytes |
| 記録 | |
| コンパイル時間 | 3,485 ms |
| コンパイル使用メモリ | 356,644 KB |
| 実行使用メモリ | 11,132 KB |
| 最終ジャッジ日時 | 2026-01-21 20:00:53 |
| 合計ジャッジ時間 | 22,548 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
#line 2 "ds/matrix.hpp"
#include <cassert>
#include <cstdint>
#include <vector>
template <typename T> struct Matrix {
int H, W;
std::vector<std::vector<T>> table;
Matrix(int h, int w) : H(h), W(w), table(h, std::vector<T>(w)) {}
Matrix(const std::vector<std::vector<T>> &v) : H((int)v.size()), W((int)v[0].size()), table(v) {}
std::vector<T> &operator[](int i) { return table[i]; }
const std::vector<T> &operator[](int i) const { return table[i]; }
static Matrix identity(int N) {
Matrix res(N, N);
for (int i = 0; i < N; i++) {
res[i][i] = 1;
}
return res;
}
Matrix &operator+=(const Matrix &rhs) {
assert(H == rhs.H && W == rhs.W && "DIMENSION must be the same");
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
table[i][j] += rhs[i][j];
}
}
return *this;
}
Matrix &operator-=(const Matrix &rhs) {
assert(H == rhs.H && W == rhs.W && "DIMENSION must be the same");
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
table[i][j] -= rhs[i][j];
}
}
return *this;
}
Matrix operator*(const Matrix &rhs) const {
assert(W == rhs.H && "MULTIPLICATION DIMENSION does not match");
Matrix res(H, rhs.W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (table[i][j] == 0) continue;
for (int k = 0; k < rhs.W; k++) {
res[i][k] += table[i][j] * rhs[j][k];
}
}
}
return res;
}
Matrix &operator*=(const Matrix &rhs) { return *this = *this * rhs; }
Matrix pow(int64_t n) const {
assert(H == W && "DIMENSION must be square");
Matrix res = identity(H);
Matrix a = *this;
while (n > 0) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
};
#line 2 "ds/segtree/segtree.hpp"
#include <algorithm>
#line 5 "ds/segtree/segtree.hpp"
template <typename Monoid> struct SegTree {
using T = typename Monoid::value_type;
int n;
std::vector<T> t;
SegTree() : n(0) {}
SegTree(int n) : n(n) { t.resize(4 * n, Monoid::e()); }
SegTree(const std::vector<T> &A) : n((int)A.size()) {
t.resize(4 * n, Monoid::e());
build(A, 1, 0, n - 1);
}
void build(const std::vector<T> &A, int v, int tl, int tr) {
if (tl == tr) {
t[v] = A[tl];
} else {
int tm = (tl + tr) / 2;
build(A, v * 2, tl, tm);
build(A, v * 2 + 1, tm + 1, tr);
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int v, int tl, int tr, int pos, const T &new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(v * 2, tl, tm, pos, new_val);
} else {
update(v * 2 + 1, tm + 1, tr, pos, new_val);
}
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int pos, const T &new_val) { update(1, 0, n - 1, pos, new_val); }
T query(int v, int tl, int tr, int l, int r) const {
if (l > r) {
return Monoid::e();
}
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return Monoid::op(query(v * 2, tl, tm, l, std::min(r, tm)),
query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r));
}
T query(int l, int r) const { return query(1, 0, n - 1, l, r); }
T get(int pos) const { return query(pos, pos); }
template <class Pred> int max_right(int l, Pred pred) const {
assert(0 <= l && l <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
return max_right_dfs(1, 0, n - 1, l, pred, acc);
}
template <class Pred> int max_right_dfs(int v, int tl, int tr, int l, Pred pred, T &acc) const {
if (tr < l) return l;
if (tl >= l) {
T nxt = Monoid::op(acc, t[v]);
if (pred(nxt)) {
acc = nxt;
return tr + 1;
}
if (tl == tr) return tl;
}
int tm = (tl + tr) / 2;
int res = max_right_dfs(v * 2, tl, tm, l, pred, acc);
if (res <= tm) return res;
return max_right_dfs(v * 2 + 1, tm + 1, tr, l, pred, acc);
}
template <class Pred> int min_left(int r, Pred pred) const {
assert(0 <= r && r <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
int res = min_left_dfs(1, 0, n - 1, r, pred, acc);
return res < 0 ? 0 : res;
}
template <class Pred> int min_left_dfs(int v, int tl, int tr, int r, Pred pred, T &acc) const {
if (tl >= r) return r;
if (tr < r) {
T nxt = Monoid::op(t[v], acc);
if (pred(nxt)) {
acc = nxt;
return tl - 1;
}
if (tl == tr) return tl + 1;
}
int tm = (tl + tr) / 2;
int res = min_left_dfs(v * 2 + 1, tm + 1, tr, r, pred, acc);
if (res >= tm + 1) return res;
return min_left_dfs(v * 2, tl, tm, r, pred, acc);
}
template <class Pred> int find_first(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_first_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_first_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_first_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
if (res != -1) return res;
return find_first_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
}
template <class Pred> int find_last(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_last_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_last_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_last_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
if (res != -1) return res;
return find_last_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
}
};
#line 4 "mod/dynamic_modint.hpp"
#include <iostream>
#include <utility>
template <int id> struct DynamicModInt {
static inline uint32_t MOD = 998244353;
uint32_t val;
static void set_mod(uint32_t m) {
assert(m > 0);
MOD = m;
}
static uint32_t get_mod() { return MOD; }
DynamicModInt() : val(0) {}
DynamicModInt(const int64_t &x) : val(x >= 0 ? x % MOD : (MOD - (-x) % MOD) % MOD) {}
uint32_t value() const { return val; }
DynamicModInt &operator+=(const DynamicModInt &rhs) {
val += rhs.val;
if (val >= MOD) val -= MOD;
return *this;
}
DynamicModInt &operator-=(const DynamicModInt &rhs) {
if (val < rhs.val) val += MOD;
val -= rhs.val;
return *this;
}
DynamicModInt &operator*=(const DynamicModInt &rhs) {
val = (uint64_t)val * rhs.val % MOD;
return *this;
}
DynamicModInt &operator/=(const DynamicModInt &rhs) { return *this *= rhs.inverse(); }
DynamicModInt operator+() const { return *this; }
DynamicModInt operator-() const { return DynamicModInt(val == 0 ? 0 : MOD - val); }
friend DynamicModInt operator+(DynamicModInt lhs, const DynamicModInt &rhs) { return lhs += rhs; }
friend DynamicModInt operator-(DynamicModInt lhs, const DynamicModInt &rhs) { return lhs -= rhs; }
friend DynamicModInt operator*(DynamicModInt lhs, const DynamicModInt &rhs) { return lhs *= rhs; }
friend DynamicModInt operator/(DynamicModInt lhs, const DynamicModInt &rhs) { return lhs /= rhs; }
friend bool operator==(const DynamicModInt &lhs, const DynamicModInt &rhs) { return lhs.val == rhs.val; }
friend bool operator!=(const DynamicModInt &lhs, const DynamicModInt &rhs) { return lhs.val != rhs.val; }
DynamicModInt pow(uint64_t n) const {
DynamicModInt res = 1, a = *this;
while (n > 0) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
DynamicModInt inverse() const {
int64_t a = val, b = MOD, u = 1, v = 0;
while (b) {
int64_t t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return DynamicModInt(u);
}
friend std::ostream &operator<<(std::ostream &os, const DynamicModInt &x) { return os << x.val; }
friend std::istream &operator>>(std::istream &is, DynamicModInt &x) {
int64_t v;
is >> v;
x = DynamicModInt(v);
return is;
}
};
#line 4 "3227.test.cpp"
#include <bits/stdc++.h>
using namespace std;
void solve() {
int K, N;
cin >> K >> N;
using dmint = DynamicModInt<0>;
dmint::set_mod(K);
using mat = Matrix<dmint>;
vector<mat> A;
for (int i = 0; i < N; i++) {
mat now(2, 2);
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
cin >> now[x][y];
}
}
A.push_back(now);
}
struct Monoid {
using value_type = mat;
static mat e() { return mat::identity(2); }
static mat op(const mat &a, const mat &b) {
mat res = a * b;
return res;
}
};
SegTree<Monoid> seg(A);
int Q;
cin >> Q;
while (Q--) {
int idx, l, r;
cin >> idx >> l >> r;
idx--, l--, r--;
mat now(2, 2);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
cin >> now[i][j];
}
}
seg.update(idx, now);
mat ans = seg.query(l, r);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
cout << ans[i][j] << " \n"[j == 1];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}