結果

問題 No.510 二次漸化式
コンテスト
ユーザー imulan
提出日時 2017-05-05 00:12:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 402 ms / 3,000 ms
コード長 2,078 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 176,708 KB
実行使用メモリ 87,424 KB
最終ジャッジ日時 2024-09-14 07:18:21
合計ジャッジ時間 11,176 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using vl = vector<ll>;
using mat = vector<vl>;

const mat E{{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
const mat I{{1,0,0,0},{0,0,0,1},{0,0,0,1},{0,0,0,1}};

const ll mod = 1e9+7;

mat mul(const mat &A, const mat &B)
{
    int n = A.size();
    mat C(n,vl(n,0));
    rep(i,n)rep(j,n)rep(k,n) (C[i][j]+=A[i][k]*B[k][j])%=mod;
    return C;
}

struct MatSegTree{
    int n; vector<mat> dat;
    //初期化
    MatSegTree(int _n){
        n=1;
        while(n<_n) n*=2;
        dat=vector<mat>(2*n-1,I);
    }
    //k番目(0-indexed)のx/yをaに変更
    void update(int k, int xy, ll a){
        k+=n-1;

        a%=mod;
        if(xy==0)
        {
            dat[k][0][2]=a;
        }
        else
        {
            dat[k][1][1]=a;
            dat[k][2][1]=(2*a)%mod;
            dat[k][2][2]=(a*a)%mod;
        }
        //更新
        while(k>0){
            k=(k-1)/2;
            dat[k]=mul(dat[2*k+1],dat[2*k+2]);
        }
    }
    //内部的に投げられるクエリ
    mat _query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return E;
        if(a<=l && r<=b) return dat[k];

        mat L=_query(a,b,2*k+1,l,(l+r)/2);
        mat R=_query(a,b,2*k+2,(l+r)/2,r);
        return mul(L,R);
    }
    //[a,b)
    mat query(int a, int b){
        return _query(a,b,0,0,n);
    }
};

int main()
{
    int n,q;
    scanf(" %d %d", &n, &q);

    MatSegTree st(n);
    while(q--)
    {
        char o;
        int i,v;
        scanf(" %c %d", &o, &i);
        if(o=='a')
        {
            ll ans=1;
            if(i>0)
            {
                mat M = st.query(n-i,n);
                ans = 0;
                rep(j,4) (ans += M[0][j])%=mod;
            }
            printf("%lld\n", ans);
        }
        else
        {
            scanf(" %d", &v);
            st.update(n-1-i,(o=='y'),v);
        }
    }
    return 0;
}
0