結果

問題 No.510 二次漸化式
ユーザー Guowen Rong
提出日時 2025-02-24 17:20:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 150 ms / 3,000 ms
コード長 3,025 bytes
コンパイル時間 2,249 ms
コンパイル使用メモリ 180,148 KB
実行使用メモリ 35,544 KB
最終ジャッジ日時 2025-02-24 17:20:27
合計ジャッジ時間 6,934 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 10, M = 4, mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
char op;
int n, q, a, v;
int x[N], y[N];
struct Mat{
	int n, m;
	int a[M][M];
	Mat(){
		n = m = 0;
		memset(a, 0, sizeof(a));
	}
	Mat(int _n, int _m){
		n = _n, m = _m;
		for(int i = 0; i < n; ++i)
		  a[i][i] = 1;
	}
	inline void init(int _n, int _m){
		n = _n, m = _m;
		memset(a, 0, sizeof(a));
	}
	inline int* operator[](int i){
		return a[i];
	}
	inline friend Mat operator*(Mat A, Mat B){
		Mat ans;
		ans.n = A.n, ans.m = B.m;
		for(int i = 0; i < A.n; ++i)
		  for(int j = 0; j < B.m; ++j)
		    for(int k = 0; k < A.m; ++k)
		      ans[i][j] = (ans[i][j] + 1ll * A[i][k] * B[k][j] % mod) % mod;
		return ans;
	}
}now;
struct Node{
	int l, r;
	Mat mul;
}X[N << 2];
inline void pushup(int k){
	X[k].mul = X[k << 1 | 1].mul * X[k << 1].mul;
}
inline void newmat(Mat &a, int x, int y){
	a.init(4, 4);
	a[0][0] = a[1][3] = a[2][3] = a[3][3] = 1;
	a[0][2] = x, a[1][1] = y, a[2][1] = 2ll * y % mod, a[2][2] = 1ll * y * y % mod;
}
inline void build(int k, int l, int r){
	X[k].l = l, X[k].r = r;
	if(l == r){
		newmat(X[k].mul, 0, 0);
		return ;
	} 
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	pushup(k);
}
inline void update(int k, int i){
	if(X[k].l == i && i == X[k].r){
		newmat(X[k].mul, x[i], y[i]);
		return ;
	}
	int mid = (X[k].l + X[k].r) >> 1;
	if(i <= mid)
	  update(k << 1, i);
	else
	  update(k << 1 | 1, i);
	pushup(k);
}
inline Mat query(int k, int l, int r){
	if(X[k].l == l && r == X[k].r)
	  return X[k].mul;
	int mid = (X[k].l + X[k].r) >> 1;
	if(r <= mid)
	  return query(k << 1, l, r);
	else if(l > mid)
	  return query(k << 1 | 1, l, r);
	else
	  return query(k << 1 | 1, mid + 1, r) * query(k << 1, l, mid);
}
bool End;
int main(){
//	open("A.in", "A.out");
	now.init(4, 1);
	now[0][0] = now[1][0] = now[2][0] = now[3][0] = 1;
	n = read(), q = read();
	build(1, 0, n);
	while(q--){
		cin >> op;
		if(op == 'x'){
			a = read(), v = read();
			x[a] = v;
			update(1, a);
		}
		else if(op == 'y'){
			a = read(), v = read();
			y[a] = v;
			update(1, a);
		}
		else{
			a = read();
			if(!a){
				puts("1");
				continue;
			}
			Mat ans = query(1, 0, a - 1) * now;
			write(ans[0][0]);
			putchar('\n');
		}
	}
	cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}
0