結果

問題 No.426 往復漸化式
ユーザー antaanta
提出日時 2016-09-23 00:24:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 56 ms / 5,000 ms
コード長 6,927 bytes
コンパイル時間 1,934 ms
コンパイル使用メモリ 182,276 KB
実行使用メモリ 44,488 KB
最終ジャッジ日時 2023-08-11 03:13:14
合計ジャッジ時間 3,519 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 14 ms
7,712 KB
testcase_06 AC 14 ms
7,548 KB
testcase_07 AC 43 ms
43,076 KB
testcase_08 AC 42 ms
43,220 KB
testcase_09 AC 53 ms
42,936 KB
testcase_10 AC 50 ms
43,732 KB
testcase_11 AC 40 ms
43,924 KB
testcase_12 AC 48 ms
43,152 KB
testcase_13 AC 56 ms
42,480 KB
testcase_14 AC 54 ms
43,212 KB
testcase_15 AC 43 ms
44,040 KB
testcase_16 AC 54 ms
43,440 KB
testcase_17 AC 56 ms
44,488 KB
testcase_18 AC 56 ms
42,424 KB
testcase_19 AC 39 ms
42,740 KB
testcase_20 AC 48 ms
42,948 KB
testcase_21 AC 54 ms
43,360 KB
testcase_22 AC 51 ms
42,960 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) {}
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;

struct NoIntitializationTag {};

template<int Height, int Width>
struct Matrix {
	typedef mint Num;
	Num v[Height][Width];
	Matrix() { memset(v, 0, sizeof(v)); }
	explicit Matrix(NoIntitializationTag) { }
	int height() const { return Height; }
	int width() const { return Width; }
	Num& at(int i, int j) { return v[i][j]; }
	const Num at(int i, int j) const { return v[i][j]; }

	template<int WidthB>
	Matrix<Height, WidthB> operator*(const Matrix<Width, WidthB>& B) const {
		int n = height(), m = B.width(), p = B.height();
		Matrix<Height, WidthB> AB(NoIntitializationTag{});
		rep(i, Height) {
			rep(j, WidthB) {
				static_assert((uint64_t)(mint::Mod - 1) * (mint::Mod - 1) <= ~(uint64_t)0 / WidthB, "(Mod-1)^2 * WidthB >= 2^64");
				uint64_t sum = 0;
				rep(k, Width)
					sum += (uint64_t)at(i, k).x * B.at(k, j).x;
				AB.v[i][j].x = sum % mint::Mod;
			}
		}
		return AB;
	}

	Matrix& operator*=(const Matrix<Width, Width>& B) {
		return *this = *this * B;
	}

	Matrix& operator+=(const Matrix& B) {
		rep(i, Height) rep(j, Width)
			at(i, j) += B.at(i, j);
		return *this;
	}

	Matrix operator+(const Matrix& B) const {
		return Matrix(*this) += B;
	}

	Matrix<Width, Height> transpose() const {
		Matrix res(NoIntitializationTag{});
		rep(i, Height) rep(j, Width)
			res.at(j, i) = at(i, j);
		return res;
	}
};

template<int Size>
inline const Matrix<Size, Size> makeIdentityMatrix() {
	Matrix<Size, Size> I;
	rep(i, Size)
		I.at(i, i) = 1;
	return I;
}

struct Val {
	Matrix<3, 3> A;
	Matrix<2, 2> B;
	Matrix<3, 2> AtoB;
	Val() : A(makeIdentityMatrix<3>()), B(makeIdentityMatrix<2>()), AtoB() {}
	explicit Val(NoIntitializationTag) : A(NoIntitializationTag{}), B(NoIntitializationTag{}), AtoB(NoIntitializationTag{}) {}

	Val operator*(const Val &that) const {
		Val res(NoIntitializationTag{});
		res.A = A * that.A;
		res.B = that.B * B;
		res.AtoB = AtoB + A * that.AtoB * B;
		return res;
	}
};

struct GetRangeSegmentTree {
	static Val combineVal(const Val &x, const Val &y) { return x * y; }
	static void assignCombineVal(Val &x, const Val &y) { x = x * y; }
	static Val identityVal() { return Val(); }

	vector<Val> nodes;
	int n;
	void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
	void init(const vector<Val> &u) {
		n = 1; while(n < (int)u.size()) n *= 2;
		nodes.resize(n, identityVal());
		nodes.insert(nodes.end(), u.begin(), u.end());
		nodes.resize(n * 2, identityVal());
		for(int i = n - 1; i > 0; -- i)
			nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
	}
	Val get(int i) {
		return nodes[i + n];
	}
	Val getWhole() const {
		return nodes[1];
	}
	Val getRange(int l, int r) const {
		Val m = identityVal();
		int indices[64]; int k = 0;
		for(; l && l + (l&-l) <= r; l += l&-l)
			assignCombineVal(m, nodes[(n + l) / (l&-l)]);
		for(; l < r; r -= r&-r)
			indices[k ++] = (n + r) / (r&-r) - 1;
		while(-- k >= 0) assignCombineVal(m, nodes[indices[k]]);
		return m;
	}
	Matrix<1, 3> getRangeA(int l, int r, Matrix<1, 3> a) const {
		int indices[64]; int k = 0;
		for(; l && l + (l&-l) <= r; l += l&-l)
			a *= nodes[(n + l) / (l&-l)].A;
		for(; l < r; r -= r&-r)
			indices[k ++] = (n + r) / (r&-r) - 1;
		while(-- k >= 0) a *= nodes[indices[k]].A;
		return a;
	}
	void set(int i, const Val &x) {
		i += n; nodes[i] = x;
		for(i >>= 1; i > 0; i >>= 1)
			nodes[i] = combineVal(nodes[i * 2], nodes[i * 2 + 1]);
	}
};

//左端の a と 右端の b から 右端の a と 左端の b を得る

int main() {
	int n;
	while(~scanf("%d", &n)) {
		Matrix<1, 3> a0;
		Matrix<1, 2> bn;
		{
			int a00; int a01; int a02;
			scanf("%d%d%d", &a00, &a01, &a02);
			int bn0; int bn1;
			scanf("%d%d", &bn0, &bn1);
			a0.at(0, 0) = a00;
			a0.at(0, 1) = a01;
			a0.at(0, 2) = a02;
			bn.at(0, 0) = bn0;
			bn.at(0, 1) = bn1;
		}

		auto getVal = [](const Matrix<3, 3> &A, const Matrix<2, 2> &B, int index) -> Val {
			Val res(NoIntitializationTag{});
			res.A = A.transpose();
			res.B = B.transpose();
			Matrix<3, 2> X(NoIntitializationTag{});
			rep(i, 2) rep(j, 3)
				X.at(j, i) = 6 * (index + 1) + (i * 3 + j);
			res.AtoB = A.transpose() * X;
			return res;
		};

		GetRangeSegmentTree segt;
		vector<Matrix<3, 3>> As(n);
		vector<Matrix<2, 2>> Bs(n);
		rep(i, n) As[i] = makeIdentityMatrix<3>();
		rep(i, n) Bs[i] = makeIdentityMatrix<2>();
		vector<Val> initValues(n);
		rep(i, n)
			initValues[i] = getVal(As[i], Bs[i], i);
		segt.init(initValues);
		int Q;
		scanf("%d", &Q);
		for(int ii = 0; ii < Q; ++ ii) {
			char ty[10];
			scanf("%s", ty);
			if(*ty == 'a') {
				int i;
				scanf("%d", &i);
				auto &A = As[i];
				rep(y, 3) rep(x, 3) {
					int a;
					scanf("%d", &a);
					A.at(y, x) = a;
				}
				segt.set(i, getVal(As[i], Bs[i], i));
			} else if(*ty == 'b') {
				int i;
				scanf("%d", &i);
				-- i;
				auto &B = Bs[i];
				rep(y, 2) rep(x, 2) {
					int b;
					scanf("%d", &b);
					B.at(y, x) = b;
				}
				segt.set(i, getVal(As[i], Bs[i], i));
			} else if(*ty == 'g' && ty[1] == 'a') {
				int i;
				scanf("%d", &i);
				auto a = segt.getRangeA(0, i, a0);
				rep(y, 3) {
					if(y != 0) putchar(' ');
					printf("%d", a.at(0, y).get());
				}
				puts("");
				fflush(stdout);
			} else if(*ty == 'g' && ty[1] == 'b') {
				int i;
				scanf("%d", &i);
				auto a = segt.getRangeA(0, i, a0);
				auto val = segt.getRange(i, n);
				auto b = a * val.AtoB + bn * val.B;
				rep(y, 2) {
					if(y != 0) putchar(' ');
					printf("%d", b.at(0, y).get());
				}
				puts("");
				fflush(stdout);
			} else abort();
		}
	}
	return 0;
}
0