結果

問題 No.426 往復漸化式
ユーザー pekempeypekempey
提出日時 2016-10-05 05:37:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 63 ms / 5,000 ms
コード長 3,484 bytes
コンパイル時間 4,303 ms
コンパイル使用メモリ 188,456 KB
実行使用メモリ 23,280 KB
最終ジャッジ日時 2023-08-13 23:04:14
合計ジャッジ時間 5,458 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
22,896 KB
testcase_01 AC 24 ms
23,020 KB
testcase_02 AC 23 ms
23,280 KB
testcase_03 AC 26 ms
23,008 KB
testcase_04 AC 25 ms
23,212 KB
testcase_05 AC 37 ms
23,060 KB
testcase_06 AC 37 ms
23,148 KB
testcase_07 AC 39 ms
22,956 KB
testcase_08 AC 40 ms
23,008 KB
testcase_09 AC 58 ms
22,992 KB
testcase_10 AC 57 ms
23,268 KB
testcase_11 AC 39 ms
23,144 KB
testcase_12 AC 53 ms
22,972 KB
testcase_13 AC 63 ms
23,152 KB
testcase_14 AC 53 ms
23,040 KB
testcase_15 AC 38 ms
23,004 KB
testcase_16 AC 53 ms
22,996 KB
testcase_17 AC 63 ms
22,972 KB
testcase_18 AC 54 ms
23,028 KB
testcase_19 AC 38 ms
22,944 KB
testcase_20 AC 51 ms
22,980 KB
testcase_21 AC 60 ms
23,024 KB
testcase_22 AC 51 ms
22,892 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
uint32_t inv;
int r2;
int one;

int reduce(uint64_t x) {
	uint64_t y = uint64_t(uint32_t(x) * inv) * mod;
	return int(x >> 32) + mod - int(y >> 32);
}

int transform(int n) {
	return reduce(int64_t(n) * r2);
}

int normalize(int n) {
	return n >= mod ? n - mod : n;
}

void init_montgomery_reduction() {
	inv = 1;
	for (int i = 0; i < 5; ++i) inv *= 2 - inv * uint32_t(mod);
	r2 = -uint64_t(mod) % mod;
	one = transform(1);
}

int modadd(int a, int b) {
	return (a += b - mod) < 0 ? a + mod : a;
}

template<int H, int W>
struct Matrix {
	int a[H][W] = {};

	static Matrix I() {
		Matrix<H, W> res;
		for (int i = 0; i < H; i++) res[i][i] = one;
		return res;
	}

	Matrix operator+(const Matrix<H, W> &b) const {
		Matrix<H, W> s;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				s.a[i][j] = modadd(a[i][j], b.a[i][j]);
			}
		}
		return s;
	}

	template<int N>
	Matrix<H, N> operator*(const Matrix<W, N> &b) const {
		Matrix<H, N> s;
		for (int i = 0; i < H; i++) {
			for (int k = 0; k < W; k++) {
				for (int j = 0; j < N; j++) {
					s[i][j] = modadd(s[i][j], reduce(int64_t(a[i][k]) * b.a[k][j]));
				}
			}
		}
		return s;
	}

	int *operator[](int i) {
		return a[i];
	}
};

const int N = 1 << 17;

struct Tuple {
	Matrix<3, 3> A;
	Matrix<2, 2> B;
	Matrix<2, 3> S;

	Tuple() {
		A = Matrix<3, 3>::I();
		B = Matrix<2, 2>::I();
	}

	Tuple(Matrix<3, 3> A, Matrix<2, 2> B, Matrix<2, 3> S) : A(A), B(B), S(S) {}

	Tuple operator*(const Tuple &r) const {
		return Tuple(r.A * A, B * r.B, S + B * r.S * A);
	}
};

Tuple seg[N * 2];

void build() {
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				seg[k + N].S[i][j] = transform(k * 6 + i * 3 + j);
			}
		}
		for (int i = 0; i < 3; i++) seg[k + N].A[i][i] = one;
		for (int i = 0; i < 2; i++) seg[k + N].B[i][i] = one;
	}
	for (int k = N - 1; k > 0; k--) {
		seg[k] = seg[k * 2 + 0] * seg[k * 2 + 1];
	}
}

void update(int k) {
	k += N;
	while (k > 1) {
		k >>= 1;
		seg[k] = seg[k * 2 + 0] * seg[k * 2 + 1];
	}
}

Tuple query(int l, int r) {
	Tuple L, R;
	for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if (l & 1) L = L * seg[l++];
		if (r & 1) R = seg[--r] * R;
	}
	return L * R;
}

int in() {
	int a;
	scanf("%d", &a);
	return a;
}

int in_t() {
	return transform(in());
}

int main() {
	init_montgomery_reduction();

	int n = in();

	Matrix<3, 1> va;
	Matrix<2, 1> vb;

	for (int i = 0; i < 3; i++) va[i][0] = in_t();
	for (int i = 0; i < 2; i++) vb[i][0] = in_t();

	build();

	int q = in();

	for (int ii = 0; ii < q; ii++) {
		char str[16];
		scanf("%s", str);

		if (str[0] == 'a') {
			int k = in();
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) seg[k + N].A[i][j] = in_t();
			}
			update(k);
		} else if (str[0] == 'b') {
			int k = in();
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) seg[k + N].B[i][j] = in_t();
			}
			update(k);
		} else if (str[1] == 'a') {
			int k = in();
			auto ans = query(0, k).A * va;
			for (int i = 0; i < 3; i++) {
				printf("%d ", normalize(reduce(ans[i][0])));
			}
			printf("\n");
		} else if (str[1] == 'b') {
			int k = in();
			auto X = query(k + 1, n + 1);
			auto Y = query(0, k + 1);
			auto ans = X.B * vb + X.S * Y.A * va;
			for (int i = 0; i < 2; i++) {
				printf("%d ", normalize(reduce(ans[i][0])));
			}
			printf("\n");
		}
	}
}
0