結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }