結果
問題 |
No.510 二次漸化式
|
ユーザー |
|
提出日時 | 2025-02-28 22:47:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 3,000 ms |
コード長 | 2,426 bytes |
コンパイル時間 | 1,640 ms |
コンパイル使用メモリ | 176,672 KB |
実行使用メモリ | 33,824 KB |
最終ジャッジ日時 | 2025-02-28 22:47:11 |
合計ジャッジ時間 | 6,024 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:103:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 103 | scanf(" %c",&op); | ~~~~~^~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();} while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch&15),ch=getchar(); return x*f; } inline void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+48); return; } inline void openfile() { freopen("16.in","r",stdin); freopen("generator.out","w",stdout); } constexpr int M=1e5+4,mod=1e9+7; int X[M],Y[M]; struct Matrix { int a[5][5]; Matrix(){} inline void clear(){memset(a,0,sizeof a);} inline void init(int id) { a[1][1]=1,a[2][2]=Y[id],a[2][3]=2*Y[id]%mod; a[3][1]=X[id],a[3][3]=1ll*Y[id]*Y[id]%mod; a[4][2]=1,a[4][3]=1,a[4][4]=1; return; } inline Matrix operator*(const Matrix&b)const { Matrix res; res.clear(); for(int k=1;k<=4;++k) for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) res.a[i][j]=(res.a[i][j]+1ll*a[i][k]*b.a[k][j]%mod)%mod; return res; } inline int value() { int res=0; for(int i=1;i<=4;++i)res=(res+a[i][1])%mod; return res; } }; struct SegmentTree { #define lson rt<<1 #define rson rt<<1|1 struct node{int l,r;Matrix vl;}tr[M<<2]; inline void update(int rt){tr[rt].vl=tr[lson].vl*tr[rson].vl;return;} inline void build(int rt,int l,int r) { tr[rt].l=l,tr[rt].r=r; if(l==r){tr[rt].vl.init(l);return;} int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); update(rt); return; } inline void modify(int rt,int pos) { int l=tr[rt].l,r=tr[rt].r; if(l==r){tr[rt].vl.init(l);return;} int mid=l+r>>1; if(pos<=mid)modify(lson,pos); if(pos>mid)modify(rson,pos); update(rt); return; } inline Matrix query(int rt,int posl,int posr) { int l=tr[rt].l,r=tr[rt].r; if(posl<=l&&r<=posr)return tr[rt].vl; Matrix res; res.clear(); for(int i=1;i<=4;++i)res.a[i][i]=1; int mid=l+r>>1; if(posl<=mid)res=res*query(lson,posl,posr); if(posr>mid)res=res*query(rson,posl,posr); return res; } #undef lson #undef rson }T; int main() { //openfile(); int n=read()+1,q=read(); T.build(1,1,n); for(int i=1;i<=q;++i) { char op; scanf(" %c",&op); int id=read(); if(op=='x')X[id+1]=read(),T.modify(1,id+1); if(op=='y')Y[id+1]=read(),T.modify(1,id+1); if(op=='a') { auto ans=T.query(1,1,id); write(ans.value()),puts(""); } } return 0; }