結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-08 22:14:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,188 ms / 8,000 ms |
コード長 | 2,560 bytes |
コンパイル時間 | 1,099 ms |
コンパイル使用メモリ | 122,684 KB |
実行使用メモリ | 42,552 KB |
最終ジャッジ日時 | 2025-08-08 22:14:56 |
合計ジャッジ時間 | 22,513 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <iostream> #include <iomanip>//小数点出力用 //cout << fixed << setprecision(10) << ans; #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <unordered_map> using ll = long long; using namespace std; #define modPHash (ll)((1LL<<61)-1) #define modP (ll)998244353 bool chkrng0idx(int pos, int sup) { return (0 <= pos && pos < sup); } int clk4(int num) { return (num - 2) * (num % 2); } void yn(bool tf) { cout << (tf ? "Yes\n" : "No\n"); } ll K; vector<vector<ll>> mul(vector<vector<ll>>& A, vector<vector<ll>>& B, int size) { vector<vector<ll>>res; for (int i = 0; i < size; i++) { vector<ll>row; for (int j = 0; j < size; j++) { ll tmp = 0; for (int k = 0; k < size; k++) { tmp += A[i][k] * B[k][j]; } row.push_back(tmp % K); } res.push_back(row); } return res; } #define segL (1<<17) vector<vector<ll>> segT[segL * 2]; int c2(int X) { int res = 0; int t = X; if (t == 0)t = segL; while (1) { if (t % 2 == 0) { t /= 2; res++; } else { break; } } return res; } void update(int idx, vector<vector<ll>>& X) { int i = idx + segL; segT[i] = X; i /= 2; while (i >= 1) { segT[i] = mul(segT[2 * i], segT[2 * i + 1], 2); i /= 2; } } vector<vector<ll>> getS(int L, int R) { int tL = L; vector<ll>I(2); vector<vector<ll>>RE(2, I); RE[0][0] = 1; RE[1][1] = 1; while (tL != R) { int b = c2(tL); for (;b >= 0;b--) { if (tL + (1 << b) <= R) { int segIdx = (tL + segL) >> b; auto tmp = mul(RE, segT[segIdx], 2); RE = tmp; tL += (1 << b); break; } } } return RE; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vector<ll>I(2); vector<vector<ll>>M(2, I); for (int i = 0;i < 2 * segL;i++) { segT[i] = M; } ll N; cin >> K >> N; for (int i = 0;i < N;i++) { ll A, B, C, D; cin >> A >> B >> C >> D; A %= K; B %= K; C %= K; D %= K; A += K; B += K; C += K; D += K; A %= K; B %= K; C %= K; D %= K; M[0][0] = A; M[0][1] = B; M[1][0] = C; M[1][1] = D; update(i, M); } ll Q; cin >> Q; while (Q--) { ll X, L, R; cin >> X >> L >> R; ll A, B, C, D; cin >> A >> B >> C >> D; A %= K; B %= K; C %= K; D %= K; A += K; B += K; C += K; D += K; A %= K; B %= K; C %= K; D %= K; M[0][0] = A; M[0][1] = B; M[1][0] = C; M[1][1] = D; update(X - 1, M); auto RES = getS(L - 1, R); cout << RES[0][0] << " " << RES[0][1] << "\n"; cout << RES[1][0] << " " << RES[1][1] << "\n"; } return 0; }