結果

問題 No.510 二次漸化式
コンテスト
ユーザー chocorusk
提出日時 2019-10-26 16:29:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 118 ms / 3,000 ms
コード長 4,779 bytes
コンパイル時間 1,287 ms
コンパイル使用メモリ 118,064 KB
実行使用メモリ 32,256 KB
最終ジャッジ日時 2024-09-14 12:30:47
合計ジャッジ時間 6,429 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<int MOD>
struct ModInt{
	int x;
	ModInt(): x(0){}
	ModInt(ll y): x(y>=0 ? y%MOD : (MOD-(-y)%MOD)%MOD){}

	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=MOD-p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1ll*x*p.x%MOD);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inv();
		return *this;
	}

	ModInt operator-() const{ return ModInt(-x);}
	ModInt operator+(const ModInt &p) const{ return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p) const{ return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p) const{ return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p) const{ return ModInt(*this)/=p;}
	bool operator==(const ModInt &p) const{ return x==p.x;}
	bool operator!=(const ModInt &p) const{ return x!=p.x;}

	ModInt pow(ll n) const{
		ModInt ret(1), p(x);
		while(n){
			if(n&1) ret*=p;
			p*=p;
			n>>=1;
		}
		return ret;
	}
	ModInt inv() const{
		return pow(MOD-2);
	}
};
const int MOD=1e9+7;
using mint=ModInt<MOD>;

template<typename T, size_t size>
struct Matrix{
    using arr=array<T, size>;
	array<arr, size> a;
	Matrix(){}
	Matrix(array<arr, size> a):a(a){}

	inline const arr &operator[](size_t k) const{
		return a[k];
	}
	inline arr &operator[](size_t k){
		return a[k];
	}

	static Matrix I(){
		Matrix mat;
		for(int i=0; i<size; i++) mat[i][i]=1;
		return mat;
	}

	Matrix &operator+=(const Matrix &b){
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				(*this)[i][j]+=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator-=(const Matrix &b){
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				(*this)[i][j]-=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator*=(const Matrix &b){
		array<arr, size> c;
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					c[i][j]+=(*this)[i][k]*b[k][j];
				}
			}
		}
		for(int i=0; i<size; i++) for(int j=0; j<size; j++) (*this)[i][j]=c[i][j];
		return (*this);
	}
	Matrix operator+(const Matrix &b) const{
		return (Matrix(*this)+=b);
	}
	Matrix operator-(const Matrix &b) const{
		return (Matrix(*this)-=b);
	}
	Matrix operator*(const Matrix &b) const{
		Matrix c;
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					c[i][j]+=(*this)[i][k]*b[k][j];
				}
			}
		}
        return c;
	}

	Matrix pow(ll k) const{
		Matrix ap(a), ret=I();
		while(k){
			if(k&1) ret*=ap;
			ap*=ap;
			k>>=1;
		}
		return ret;
	}
};

template<typename Monoid>
struct SegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	int sz;
	vector<Monoid> seg;
	const F f;
	const Monoid e;

	SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
	}

	SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
		for(int i=0; i<n; i++) seg[i+sz]=v[i];
		for(int i=sz-1; i>=1; i--){
			seg[i]=f(seg[2*i], seg[2*i+1]);
		}
	}

	void update(int k, const Monoid &x){
		k+=sz;
		seg[k]=x;
		while(k>1){
			k>>=1;
			seg[k]=f(seg[2*k], seg[2*k+1]);
		}
	}

	Monoid query(int a, int b){
		a+=sz, b+=sz;
		Monoid ret=e;
		for(;a<b; a>>=1, b>>=1){
			if(b&1) ret=f(seg[--b], ret);
			if(a&1) ret=f(ret, seg[a++]);
		}
		return ret;
	}

	Monoid operator[](const int &k) const{
		return seg[k+sz];
	}
};
int main()
{
    using Mat=Matrix<mint, 4>;
    Mat id;
    id[0][0]=id[1][3]=id[2][3]=id[3][3]=1;
    int n;
    cin>>n;
    vector<Mat> v(n, id);
    SegmentTree<Mat> seg(n, [](Mat a, Mat b){ return b*a;}, Mat::I(), v);
    int q;
    cin>>q;
    for(int i=0; i<q; i++){
        char c; cin>>c;
        if(c=='x'){
            int p; mint val;
            cin>>p>>val.x;
            v[p][0][1]=val;
            seg.update(p, v[p]);
        }else if(c=='y'){
            int p; mint val;
            cin>>p>>val.x;
            v[p][1][1]=val*val, v[p][1][2]=val*mint(2), v[p][2][2]=val;
            seg.update(p, v[p]);
        }else{
            int p; cin>>p;
            Mat mat=seg.query(0, p);
            cout<<(mat[0][0]+mat[0][1]+mat[0][2]+mat[0][3]).x<<endl;
        }
    }
    return 0;
}
0