結果

問題 No.426 往復漸化式
ユーザー antaanta
提出日時 2016-09-22 23:44:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 135 ms / 5,000 ms
コード長 6,922 bytes
コンパイル時間 2,441 ms
コンパイル使用メモリ 191,464 KB
実行使用メモリ 73,004 KB
最終ジャッジ日時 2024-11-17 15:32:18
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 6 ms
6,816 KB
testcase_04 AC 6 ms
6,816 KB
testcase_05 AC 32 ms
10,956 KB
testcase_06 AC 31 ms
10,972 KB
testcase_07 AC 94 ms
72,304 KB
testcase_08 AC 94 ms
71,596 KB
testcase_09 AC 119 ms
71,484 KB
testcase_10 AC 118 ms
72,384 KB
testcase_11 AC 90 ms
72,068 KB
testcase_12 AC 106 ms
72,428 KB
testcase_13 AC 126 ms
71,624 KB
testcase_14 AC 119 ms
72,012 KB
testcase_15 AC 90 ms
71,912 KB
testcase_16 AC 115 ms
71,616 KB
testcase_17 AC 128 ms
72,732 KB
testcase_18 AC 124 ms
71,724 KB
testcase_19 AC 91 ms
71,884 KB
testcase_20 AC 116 ms
71,704 KB
testcase_21 AC 135 ms
73,004 KB
testcase_22 AC 113 ms
71,652 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 Matrix {
	typedef mint Num;
	static const int MaxN = 3;
	int hei, wid;
	Num v[MaxN][MaxN];
	Matrix() {}
	Matrix(int n, int m) : hei(n), wid(m) {
		memset(v, 0, sizeof(v));
	}
	inline int height() const { return hei; }
	inline int width() const { return wid; }
	inline Num& at(int i, int j) { return v[i][j]; }
	inline const Num& at(int i, int j) const { return v[i][j]; }
	static Matrix identity(int n) {
		Matrix A(n, n);
		rep(i, n) A.at(i, i) = 1;
		return A;
	}
	inline static Matrix identity(const Matrix& A) { return identity(A.height()); }
	Matrix& operator*=(const Matrix& B) {
		int n = height(), m = B.width(), p = B.height();
		assert(p == width());
		const unsigned(*b)[MaxN] = reinterpret_cast<const unsigned(*)[MaxN]>(B.v);
		Num w[MaxN][MaxN];
		unsigned long long pp = (1ULL << 32) % mint::Mod;
		rep(i, n) {
			const unsigned *ai = reinterpret_cast<const unsigned*>(v[i]);
			rep(j, m) {
				unsigned x0 = 0; unsigned long long x1 = 0;
				rep(k, p) {
					unsigned long long y = (unsigned long long)ai[k] * b[k][j];
					unsigned long long t = x0 + y;
					x1 += t >> 32;
					x0 = t & 0xffffffff;
				}
				w[i][j].x = (x0 + x1 % mint::Mod * pp) % mint::Mod;
			}
		}
		memcpy(v, w, sizeof(v));
		wid = m;
		return *this;
	}

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

	Matrix& operator+=(const Matrix& B) {
		int n = height(), m = width();
		assert(n == B.height() && m == B.width());
		rep(i, n) rep(j, m)
			at(i, j) += B.at(i, j);
		return *this;
	}

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

	Matrix getSubmatrix(int top, int left, int bot, int right) const {
		Matrix res(bot - top, right - left);
		rep(i, bot - top) rep(j, right - left)
			res.at(i, j) = at(top + i, left + j);
		return res;
	}

	Matrix transpose() const {
		Matrix res(wid, hei);
		rep(i, hei) rep(j, wid)
			res.at(j, i) = at(i, j);
		return res;
	}
};

struct Val {
	Matrix A, B, AtoB;
	Val() : A(Matrix::identity(3)), B(Matrix::identity(2)), AtoB(3, 2) {}
	explicit Val(bool) {}

	Val operator*(const Val &that) const {
		Val res(true);
		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;
	}
	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 a0(1, 3), bn(1, 2);
		{
			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 &A, const Matrix &B, int index) -> Val {
			Val res(true);
			res.A = A.transpose();
			res.B = B.transpose();
			Matrix X(3, 2);
			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> As(n), Bs(n);
		rep(i, n) As[i] = Matrix::identity(3);
		rep(i, n) Bs[i] = Matrix::identity(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);
				Matrix A(3, 3);
				rep(y, 3) rep(x, 3) {
					int a;
					scanf("%d", &a);
					A.at(y, x) = a;
				}
				As[i] = A;
				segt.set(i, getVal(As[i], Bs[i], i));
			} else if(*ty == 'b') {
				int i;
				scanf("%d", &i);
				-- i;
				Matrix B(2, 2);
				rep(y, 2) rep(x, 2) {
					int b;
					scanf("%d", &b);
					B.at(y, x) = b;
				}
				Bs[i] = B;
				segt.set(i, getVal(As[i], Bs[i], i));
			} else if(*ty == 'g' && ty[1] == 'a') {
				int i;
				scanf("%d", &i);
				Matrix A = segt.getRange(0, i).A;
				Matrix a = a0;
				a *= A;
				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);
				Matrix A = segt.getRange(0, i).A;
				Val val = segt.getRange(i, n);
				Matrix a = a0;
				a *= A;
				Matrix res = a * val.AtoB + bn * val.B;
				rep(y, 2) {
					if(y != 0) putchar(' ');
					printf("%d", res.at(0, y).get());
				}
				puts("");
				fflush(stdout);
			} else abort();
		}
	}
	return 0;
}
0