結果

問題 No.3227 Matrix Query
コンテスト
ユーザー Cafe1942
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0