結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-10 18:10:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 704 ms / 8,000 ms |
コード長 | 3,948 bytes |
コンパイル時間 | 787 ms |
コンパイル使用メモリ | 67,920 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-10 18:10:23 |
合計ジャッジ時間 | 15,291 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:165:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 165 | scanf("%d%d", &k, &n); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:173:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 173 | scanf("%d", &qn); | ~~~~~^~~~~~~~~~~ main.cpp:177:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 177 | scanf("%d%d%d", &i, &l, &r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp: In static member function ‘static Mat2<T> Mat2<T>::read() [with T = MI]’: main.cpp:80:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 80 | scanf("%d%d%d%d", &w, &x, &y, &z); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3227.cc: No.3227 Matrix Query - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ /* typedef */ using ll = long long; struct MI { static long long MOD; long long v; MI(): v() {} MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return (int)v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(long long n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; ll MI::MOD = 1; using mi = MI; template <typename T> struct Vec2 { T a, b; Vec2(): a(), b() {}; Vec2(T _a, T _b): a(_a), b(_b) {}; static Vec2 read() { int x, y; scanf("%d%d", &x, &y); return Vec2(x, y); } }; using vec2 = Vec2<mi>; template <typename T> struct Mat2 { T a, b, c, d; Mat2(): a(), b(), c(), d() {} Mat2(T _a, T _b, T _c, T _d): a(_a), b(_b), c(_c), d(_d) {} static Mat2 unit() { return Mat2(1, 0, 0, 1); } static Mat2 read() { int w, x, y, z; scanf("%d%d%d%d", &w, &x, &y, &z); return Mat2(T(w), T(x), T(y), T(z)); } bool operator==(const Mat2 &e) const { return a == e.a && b == e.b && c == e.c && d == e.d; } Mat2 operator*(const Mat2 &e) const { return Mat2(a * e.a + b * e.c, a * e.b + b * e.d, c * e.a + d * e.c, c * e.b + d * e.d); } Vec2<T> operator*(const Vec2<T> &v) const { return Vec2<T>(a * v.a + b * v.b, c * v.a + d * v.b); } Mat2 operator^(long long b) const { Mat2 p = Mat2::unit(); Mat2 a = *this; while (b > 0) { if (b & 1) p = p * a; a = a * a; b >>= 1; } return p; } T det() const { return a * d - b * c; } }; using mat2 = Mat2<mi>; template <typename T> struct SegTreeMul { int e2; vector<T> nodes; T defv; SegTreeMul() {} void init(int n, T _defv) { defv = _defv; for (e2 = 1; e2 < n; e2 <<= 1); nodes.assign(e2 * 2, defv); } T &geti(int i) { return nodes[e2 - 1 + i]; } void seti(int i, T v) { geti(i) = v; } void setall() { for (int j = e2 - 2; j >= 0; j--) nodes[j] = nodes[j * 2 + 1] * nodes[j * 2 + 2]; } void set(int i, T v) { int j = e2 - 1 + i; nodes[j] = v; while (j > 0) { j = (j - 1) / 2; nodes[j] = nodes[j * 2 + 1] * nodes[j * 2 + 2]; } } T mul_range(int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return defv; if (r0 <= i0 && i1 <= r1) return nodes[k]; int im = (i0 + i1) / 2; T v0 = mul_range(r0, r1, k * 2 + 1, i0, im); T v1 = mul_range(r0, r1, k * 2 + 2, im, i1); return v0 * v1; } T mul_range(int r0, int r1) { return mul_range(r0, r1, 0, 0, e2); } }; /* global variables */ SegTreeMul<mat2> st; /* subroutines */ /* main */ int main() { int k, n; scanf("%d%d", &k, &n); mi::MOD = k; st.init(n, mat2::unit()); for (int i = 0; i < n; i++) st.seti(i, mat2::read()); st.setall(); int qn; scanf("%d", &qn); while (qn--) { int i, l, r; scanf("%d%d%d", &i, &l, &r); i--, l--; st.set(i, mat2::read()); auto e = st.mul_range(l, r); printf("%d %d\n%d %d\n", (int)e.a, (int)e.b, (int)e.c, (int)e.d); } return 0; }