#249969 (C++14) No.510 二次漸化式

提出ソース

結果

問題	No.510 二次漸化式
ユーザー	anta
提出日時	2018-04-06 19:19:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	89 ms / 3,000 ms
コード長	4,941 bytes
コンパイル時間	2,031 ms
コンパイル使用メモリ	176,008 KB
実行使用メモリ	37,352 KB
最終ジャッジ日時	2023-09-08 18:03:16
合計ジャッジ時間	6,275 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	29 ms 4,376 KB
testcase_03	AC	28 ms 4,376 KB
testcase_04	AC	27 ms 4,376 KB
testcase_05	AC	28 ms 4,376 KB
testcase_06	AC	41 ms 7,056 KB
testcase_07	AC	41 ms 6,812 KB
testcase_08	AC	40 ms 7,044 KB
testcase_09	AC	40 ms 6,812 KB
testcase_10	AC	14 ms 4,380 KB
testcase_11	AC	14 ms 4,380 KB
testcase_12	AC	14 ms 4,376 KB
testcase_13	AC	14 ms 4,380 KB
testcase_14	AC	14 ms 4,380 KB
testcase_15	AC	15 ms 4,376 KB
testcase_16	AC	55 ms 36,464 KB
testcase_17	AC	57 ms 36,568 KB
testcase_18	AC	54 ms 35,972 KB
testcase_19	AC	56 ms 36,756 KB
testcase_20	AC	57 ms 37,004 KB
testcase_21	AC	54 ms 36,564 KB
testcase_22	AC	55 ms 37,352 KB
testcase_23	AC	77 ms 36,460 KB
testcase_24	AC	77 ms 35,672 KB
testcase_25	AC	77 ms 35,524 KB
testcase_26	AC	76 ms 35,924 KB
testcase_27	AC	77 ms 36,996 KB
testcase_28	AC	78 ms 36,480 KB
testcase_29	AC	77 ms 36,224 KB
testcase_30	AC	76 ms 36,716 KB
testcase_31	AC	88 ms 36,760 KB
testcase_32	AC	88 ms 36,032 KB
testcase_33	AC	89 ms 37,000 KB
testcase_34	AC	59 ms 36,468 KB
testcase_35	AC	52 ms 36,392 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 4;
	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;
	}
};

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

	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]);
	}
};




int main() {
	int N; int Q;
	while (~scanf("%d%d", &N, &Q)) {
		//b_{i+1}^2 = (y_i b_i + 1)^2 = y_i^2 b_i^2 + 2 y_i b_i + 1
		auto getMatrix = [](mint x, mint y) -> Matrix {
			Matrix A(4, 4);
			//1 -> 1
			A.at(0, 0) = 1;
			//b_{i+1}
			A.at(1, 1) = y;
			A.at(0, 1) = 1;
			//b_{i+1}^2
			A.at(2, 2) = y * y;
			A.at(1, 2) = y * 2;
			A.at(0, 2) = 1;
			//a_{i+1}
			A.at(3, 3) = 1;
			A.at(2, 3) = x;
			return A;
		};
		GetRangeSegmentTree segt;
		segt.init(N, getMatrix(0, 0));
		vector<mint> xs(N), ys(N);
		for (int ii = 0; ii < Q; ++ ii) {
			char ty[10];
			scanf("%s", ty);
			if (*ty == 'x' || *ty == 'y') {
				int i; int v;
				scanf("%d%d", &i, &v);
				(*ty == 'x' ? xs[i] : ys[i]) = v;
				segt.set(i, getMatrix(xs[i], ys[i]));
			} else if (*ty == 'a') {
				int i;
				scanf("%d", &i);
				auto A = segt.getRange(0, i);
				Matrix v(1, 4);
				v.at(0, 0) = 1;
				v.at(0, 1) = 1;
				v.at(0, 2) = 1;
				v.at(0, 3) = 1;
				v *= A;
				mint ans = v.at(0, 3);
				printf("%d\n", ans.get());
			} else abort();
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード