結果
問題 |
No.510 二次漸化式
|
ユーザー |
![]() |
提出日時 | 2025-02-24 16:44:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 383 ms / 3,000 ms |
コード長 | 1,465 bytes |
コンパイル時間 | 3,791 ms |
コンパイル使用メモリ | 276,384 KB |
実行使用メモリ | 55,156 KB |
最終ジャッジ日時 | 2025-02-24 16:44:57 |
合計ジャッジ時間 | 13,519 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> #define int long long using namespace std; const int N=100005,mod=1e9+7; int n,q,x[N],y[N];string op; struct matrix { int c[4][4]; matrix(){memset(c,0,sizeof(c));} matrix operator*(const matrix &p)const { matrix q; for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)(q.c[i][j]+=c[i][k]*p.c[k][j])%=mod; return q; } }sta,res,zh[N<<2]; matrix getmat(int x,int y) { matrix z; z.c[0][0]=z.c[3][1]=z.c[3][2]=z.c[3][3]=1; z.c[1][0]=x;z.c[1][1]=y*y%mod; z.c[2][1]=2*y%mod;z.c[2][2]=y; return z; } void update(int u,int l,int r,int p,matrix w) { if(p<l||p>r)return; if(l==r){zh[u]=w;return;} int mid=l+r>>1; update(u<<1,l,mid,p,w); update(u<<1|1,mid+1,r,p,w); zh[u]=zh[u<<1]*zh[u<<1|1]; } matrix query(int u,int l,int r,int L,int R) { if(r<L||l>R) { matrix I; for(int i=0;i<4;i++)I.c[i][i]=1; return I; } if(L<=l&&r<=R)return zh[u]; int mid=l+r>>1; return query(u<<1,l,mid,L,R)*query(u<<1|1,mid+1,r,L,R); } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>q; for(int i=0;i<4;i++)sta.c[0][i]=1; for(int i=1;i<=n;i++)update(1,1,n,i,getmat(0,0)); for(int i=1,p,v;i<=q;i++) { cin>>op>>p; if(op=="x") { cin>>v; update(1,1,n,p+1,getmat(v,y[p])); x[p]=v; } if(op=="y") { cin>>v; update(1,1,n,p+1,getmat(x[p],v)); y[p]=v; } if(op=="a") { if(p==0)cout<<"1\n"; else { res=sta*query(1,1,n,1,p); cout<<res.c[0][0]<<'\n'; } } } }