結果

問題 No.510 二次漸化式
ユーザー vjudge1
提出日時 2025-02-23 13:37:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,883 bytes
コンパイル時間 1,802 ms
コンパイル使用メモリ 163,136 KB
実行使用メモリ 163,860 KB
最終ジャッジ日時 2025-02-23 13:38:08
合計ジャッジ時間 13,586 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 19 RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#define DEBUG
const int N=1e5+10,Mod=1e9+7; int x[N],y[N];
struct Matrix {
    int a[10][10];
    Matrix() { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) a[i][j]=0; }
    void build(int i) { a[1][1]=a[4][2]=a[4][3]=a[4][4]=1,a[2][2]=y[i],a[2][3]=2*y[i]%Mod,a[3][1]=x[i],a[3][3]=1ll*y[i]*y[i]%Mod; }
};
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for(int k=1;k<=4;k++) for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) (c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%Mod)%=Mod;
    return c;
}
struct SGT { int l,r; Matrix w; }t[N<<2];
void pushup(int u) { t[u].w=t[u<<1].w*t[u<<1|1].w; }
void build(int u,int l,int r) {
    t[u].l=l,t[u].r=r;
    if(l==r) return t[u].w.build(l),void();
    int m=(l+r)>>1; build(u<<1,l,m),build(u<<1|1,m+1,r);
    pushup(u);
}
void update(int u,int x) {
    if(t[u].l==t[u].r) return t[u].w.build(t[u].l),void();
    int m=(t[u].l+t[u].r)>>1;
    if(x<=m) update(u<<1,x);
    else update(u<<1|1,x);
    pushup(u);
}
Matrix query(int u,int l,int r) {
    if(l<=t[u].l&&t[u].r<=r) return t[u].w;
    Matrix ans;
    for(int i=1;i<=4;i++) ans.a[i][i]=1;
    if(l<=t[u<<1].r) ans=ans*query(u<<1,l,r);
    if(r>=t[u<<1|1].l) ans=ans*query(u<<1|1,l,r);
    return ans;
}
int main() {
    //freopen("generator.in","r",stdin);
    //freopen("generator.out","w",stdout);
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int n,q; std::cin>>n>>q,n++,build(1,1,n);
    while(q--) {
        char opt; int p,q; std::cin>>opt>>p,p++;
        if(opt!='a') std::cin>>q;
        if(opt=='x') x[p]=q,update(1,p);
        if(opt=='y') y[p]=q,update(1,p);
        if(opt=='a') {
            if(!p) std::cout<<"1\n";
            else {
                Matrix ans=query(1,1,p-1); int sum=0;
                for(int i=1;i<=4;i++) (sum+=ans.a[i][1])%=Mod;
                std::cout<<sum<<'\n';
            }
        }
    }
    return 0;
}
0