結果

問題 No.3227 Matrix Query
コンテスト
ユーザー jiangxinyang
提出日時 2025-08-08 23:15:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 719 ms / 8,000 ms
コード長 2,033 bytes
コンパイル時間 2,109 ms
コンパイル使用メモリ 202,176 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-08-08 23:15:20
合計ジャッジ時間 16,712 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
struct Mat {
    ll a, b, c, d;
    Mat() : a(1), b(0), c(0), d(1) {}
    Mat(ll a, ll b, ll c, ll d) : a(a), b(b), c(c), d(d) {}
};
ll K;
ll cal(ll x) {
    return (x % K + K) % K;
}
Mat mul(Mat A, Mat B) {
    Mat C;
    C.a = (ll)(((__int128)A.a * B.a + (__int128)A.b * B.c) % K);
    C.b = (ll)(((__int128)A.a * B.b + (__int128)A.b * B.d) % K);
    C.c = (ll)(((__int128)A.c * B.a + (__int128)A.d * B.c) % K);
    C.d = (ll)(((__int128)A.c * B.b + (__int128)A.d * B.d) % K);
    return C;
}
int main() {
    int n;
    cin >> K >> n;
    vector<Mat> vec;
    for (int i = 0; i < n; i++) {
        ll x1, x2, x3, x4;
        cin >> x1 >> x2 >> x3 >> x4;
        vec.push_back({cal(x1), cal(x2), cal(x3), cal(x4)});
    }
    int sz = 1;
    while (sz < n) sz <<= 1;
    vector<Mat> seg(sz << 1);
    for (int i = 0; i < sz; i++) {
        if (i < n) {
            seg[sz + i] = vec[i];
        } else {
            seg[sz + i] = Mat(1 % K, 0, 0, 1 % K);
        }
    }
    for (int i = sz - 1; i >= 1; i--) seg[i] = mul(seg[i << 1], seg[i << 1 | 1]);
    int _;
    cin >> _;
    while (_--) {
        int id, L, R;
        cin >> id >> L >> R;
        ll ya, yb, yc, yd;
        cin >> ya >> yb >> yc >> yd;
        Mat Y(cal(ya), cal(yb), cal(yc), cal(yd));
        int pos = sz + id - 1;
        seg[pos] = Y;
        pos >>= 1;
        while (pos >= 1) {
            seg[pos] = mul(seg[pos << 1], seg[pos << 1 | 1]);
            pos >>= 1;
        }
        int l = L - 1 + sz, r = R + sz;
        Mat resL(1 % K, 0, 0, 1 % K), resR(1 % K, 0, 0, 1 % K);
        while (l < r) {
            if (l & 1) resL = mul(resL, seg[l++]);
            if (r & 1) resR = mul(seg[--r], resR);
            l >>= 1;
            r >>= 1;
        }
        Mat ans = mul(resL, resR);
        cout << ans.a << " " << ans.b << "\n";
        cout << ans.c << " " << ans.d << "\n";
    }
    return 0;
}
0