結果

問題 No.510 二次漸化式
ユーザー CZS_AK_IOI2025
提出日時 2025-03-02 16:46:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,708 bytes
コンパイル時間 1,752 ms
コンパイル使用メモリ 168,352 KB
実行使用メモリ 161,380 KB
最終ジャッジ日時 2025-03-02 16:47:06
合計ジャッジ時間 8,212 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 4 WA * 30
権限があれば一括ダウンロードができます

ソースコード

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[6][6];}spj;
inline 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<=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;
	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];tree[id].hang=tree[id].lie=4;
    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;sign Czs=query(id<<1,l,mid,tol,tor)*query(id<<1|1,mid+1,r,tol,tor);
    Czs.hang=Czs.lie=4;
    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[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;memset(spj.block,0,sizeof spj.block);
    spj.block[4][1]=spj.block[3][1]=spj.block[2][1]=spj.block[1][1]=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=1;for(int i=1;i<=4;++i)ans.block[i][1]=1;
            ans=query(1,1,n+1,1,noi)*ans;
            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