結果

問題 No.510 二次漸化式
コンテスト
ユーザー vjudge1
提出日時 2025-03-02 16:11:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,480 bytes
コンパイル時間 3,612 ms
コンパイル使用メモリ 279,432 KB
実行使用メモリ 60,764 KB
最終ジャッジ日時 2025-03-02 16:12:00
合計ジャッジ時間 8,895 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 3 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
const int mod=1e9+7;
int n,m;
struct sign{int hang,lie,block[5][5];}spj;
sign operator*(const sign &a,const sign &b){
	sign c;
	c.hang=a.lie;c.lie=b.hang;
	for(int i=1;i<=c.hang;++i)
	for(int j=1;j<=c.lie;++j)
	c.block[i][j]=0;
	for(int i=1;i<=c.hang;++i)
	for(int j=1;j<=c.lie;++j)
	for(int k=1;k<=a.lie;++k)
	c.block[i][j]=(c.block[i][j]+a.block[i][k]*b.block[k][j])%mod;
	return c;
}
sign tree[maxn*6],e,ans;
inline void build(int id,int l,int r){
    tree[id].hang=tree[id].lie=4;
    memset(tree[id].block,0,sizeof tree[id].block);
    tree[id].block[1][1]=tree[id].block[2][4]=tree[id].block[3][4]=tree[id].block[4][4]=1;
    // tree[id<<1]=tree[id<<1|1]=e;
    if(l==r)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 sign 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;
    return query(id<<1,l,mid,tol,tor)*query(id<<1|1,mid+1,r,tol,tor);
}
inline void update(int id,int l,int r,int p,int val,int op){
    if(l==r){
        if(op==1)tree[id].block[1][3]=val;
        else{
            tree[id].block[2][2]=val;
            tree[id].block[3][2]=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 main(){
    // 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;spj.hang=4;spj.lie=1;
    spj.block[4][1]=spj.block[3][1]=spj.block[2][1]=spj.block[1][1]=1;
    cin>>n>>m;build(1,1,n);
    for(int ioi=1;ioi<=m;++ioi){
        char czs;cin>>czs;
        if(czs=='a'){
            int noi;cin>>noi;
            if(noi==0){
                cout<<0<<"\n";
                continue;
            }
            ans=query(1,1,n,1,noi)*spj;
            cout<<ans.block[1][1]<<"\n";
        }
        else if(czs=='x'){
            int id,val;cin>>id>>val;++id;
            update(1,1,n,id,val,1);
        }
        else if(czs=='y'){
            int id,val;cin>>id>>val;++id;
            update(1,1,n,id,val,2);
        }
    }
	return 0;
}
0