結果

問題 No.510 二次漸化式
コンテスト
ユーザー vjudge1
提出日時 2025-03-02 17:11:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 331 ms / 3,000 ms
コード長 2,833 bytes
コンパイル時間 4,450 ms
コンパイル使用メモリ 276,284 KB
実行使用メモリ 361,548 KB
最終ジャッジ日時 2025-03-02 17:11:32
合計ジャッジ時間 13,762 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
const int mod=1e9+7;
int n,m,x[maxn],y[maxn];
struct Matrix{
    int hang,lie,block[6][6];
    Matrix(){memset(block,0,sizeof block);}
    inline void init(int x,int y){
        block[1][1]=1,block[1][2]=0,block[1][3]=0,block[1][4]=0,
        block[2][1]=0,block[2][2]=y,block[2][3]=y*2%mod,block[2][4]=0,
        block[3][1]=x,block[3][2]=0,block[3][3]=y*y%mod,block[3][4]=0,
        block[4][1]=0,block[4][2]=1,block[4][3]=1,block[4][4]=1;
    }
}spj;
inline Matrix operator *(const Matrix &a,const Matrix &b){
	Matrix c;c.hang=4;c.lie=4;
	for(int i=1;i<=4;++i)
	for(int j=1;j<=4;++j)
	c.block[i][j]=0;
	for(int i=1;i<=4;++i)
	for(int j=1;j<=4;++j)
	for(int k=1;k<=4;++k)
	c.block[i][j]=(c.block[i][j]+a.block[i][k]*b.block[k][j]%mod)%mod;
	return c;
}
Matrix tree[maxn*6],e,ans;
inline void build(int id,int l,int r){
    tree[id].hang=tree[id].lie=4;
    if(l==r){
        tree[id].init(0,0);
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    tree[id]=tree[id<<1]*tree[id<<1|1];
    return;
}
inline Matrix query(int id,int l,int r,int tol,int tor){
    if(l>tor||r<tol)return e;
    if(tol<=l&&r<=tor)return tree[id];
    int mid=(l+r)>>1;
    Matrix Czs=query(id<<1,l,mid,tol,tor)*query(id<<1|1,mid+1,r,tol,tor);
    return Czs;
}
inline void update(int id,int l,int r,int p,int val,int op){
    if(l==r){
        if(op==1)tree[id].block[3][1]=val;
        else{
            tree[id].block[2][2]=val;
            tree[id].block[2][3]=(val*2)%mod;
            tree[id].block[3][3]=(val*val)%mod;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(id<<1,l,mid,p,val,op);
    else update(id<<1|1,mid+1,r,p,val,op);
    tree[id]=tree[id<<1]*tree[id<<1|1];
    return;
}
signed/*CZS ak NOI*/main(/*ChenZhuangShiYuJingXuan*/){
    // freopen("generator.in","r",stdin);
	// freopen("generator.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	e.hang=e.lie=4;memset(e.block,0,sizeof e.block);
    for(int i=1;i<=4;++i)e.block[i][i]=1;
    cin>>n>>m;build(1,1,n+1);
    for(int ioi=1;ioi<=m;++ioi){
        char czs;cin>>czs;
        if(czs=='a'){
            int noi;cin>>noi;
            if(noi==0){
                cout<<1<<"\n";
                continue;
            }
            memset(ans.block,0,sizeof ans.block);
            ans.hang=4;ans.lie=4;
            for(int i=1;i<=4;++i)ans.block[1][i]=1;
            ans=ans*query(1,1,n+1,1,noi);
            cout<<ans.block[1][1]<<"\n";
        }
        else if(czs=='x'){
            int id,val;cin>>id>>val;++id;
            update(1,1,n+1,id,val,1);
        }
        else if(czs=='y'){
            int id,val;cin>>id>>val;++id;
            update(1,1,n+1,id,val,0);
        }
    }
	return 0;
}
0