結果

問題 No.510 二次漸化式
ユーザー vjudge1
提出日時 2025-02-23 10:52:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 227 ms / 3,000 ms
コード長 2,021 bytes
コンパイル時間 1,827 ms
コンパイル使用メモリ 159,968 KB
実行使用メモリ 216,088 KB
最終ジャッジ日時 2025-02-23 10:52:33
合計ジャッジ時間 9,314 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int N = 100010, mod = 1e9 + 7;

int n, T, x[N], y[N];

struct Mat
{
	int n, a[10][10];
	void init1()
	{
		for (int i = 1; i <= n; i ++ )
			for (int j = 1; j <= n; j ++ ) a[i][j] = 0;
	}
	void init2()
	{
		init1();
		for (int i = 1; i <= n; i ++ )
			a[i][i] = 1;
	}
	void init(int i)
	{
		init1();
		a[1][1] = 1;
		a[2][2] = y[i], a[2][3] = 2 * y[i] % mod;
		a[3][1] = x[i], a[3][3] = y[i] * y[i] % mod;
		a[4][2] = a[4][3] = a[4][4] = 1;
	}
	Mat operator * (const Mat& _) const
	{
		Mat res;
		res.n = n, res.init1();
		for (int k = 1; k <= n; k ++ )
			for (int i = 1; i <= n; i ++ )
				for (int j = 1; j <= n; j ++ )
					res.a[i][j] = (res.a[i][j] + a[i][k] * _.a[k][j]) % mod;
		return res;
	}
};

struct Node
{
	int l, r;
	Mat mat;
}tr[N << 2];

void pushup(int u)
{
	tr[u].mat = tr[u << 1].mat * tr[u << 1 | 1].mat;
}

void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r, tr[u].mat.n = 4;
	if (l == r)
	{
		tr[u].mat.init(l);
		return;
	} 
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int x)
{
	if (tr[u].l == tr[u].r)
	{
		tr[u].mat.init(x);
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if (x <= mid) modify(u << 1, x);
	else modify(u << 1 | 1, x); 
	pushup(u);
}

Mat query(int u, int l, int r)
{
	if (l <= tr[u].l && tr[u].r <= r) return tr[u].mat;
	Mat res;
	res.n = 4, res.init2();
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid) res = query(u << 1, l, r);
	if (r > mid) res = res * query(u << 1 | 1, l, r);
	return res;
}

void solve()
{
	char op;
	int a, b;
	cin >> op >> a; a ++ ;
	if (op == 'x') cin >> b, x[a] = b, modify(1, a);
	else if (op == 'y') cin >> b, y[a] = b, modify(1, a);
	else
	{
		Mat m = query(1, 1, a - 1);
		cout << (m.a[1][1] + m.a[2][1] + m.a[3][1] + m.a[4][1]) % mod << "\n";
	}
}

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> T;
	n ++ ;
	build(1, 1, n);
	while (T -- ) solve();
	return 0;
}
0