結果
| 問題 |
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];
}
}
}
}