結果

問題 No.510 二次漸化式
ユーザー imulanimulan
提出日時 2017-05-05 00:12:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 397 ms / 3,000 ms
コード長 2,078 bytes
コンパイル時間 1,634 ms
コンパイル使用メモリ 174,736 KB
実行使用メモリ 87,420 KB
最終ジャッジ日時 2023-10-12 08:11:57
合計ジャッジ時間 10,939 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 113 ms
4,352 KB
testcase_03 AC 112 ms
4,352 KB
testcase_04 AC 112 ms
4,352 KB
testcase_05 AC 112 ms
4,348 KB
testcase_06 AC 192 ms
13,668 KB
testcase_07 AC 190 ms
13,616 KB
testcase_08 AC 194 ms
13,612 KB
testcase_09 AC 191 ms
13,552 KB
testcase_10 AC 41 ms
4,348 KB
testcase_11 AC 42 ms
4,352 KB
testcase_12 AC 41 ms
4,352 KB
testcase_13 AC 42 ms
4,352 KB
testcase_14 AC 41 ms
4,348 KB
testcase_15 AC 42 ms
4,348 KB
testcase_16 AC 241 ms
87,148 KB
testcase_17 AC 239 ms
87,132 KB
testcase_18 AC 238 ms
87,136 KB
testcase_19 AC 238 ms
87,160 KB
testcase_20 AC 239 ms
87,392 KB
testcase_21 AC 242 ms
87,168 KB
testcase_22 AC 237 ms
87,136 KB
testcase_23 AC 363 ms
87,128 KB
testcase_24 AC 364 ms
87,132 KB
testcase_25 AC 366 ms
87,420 KB
testcase_26 AC 373 ms
87,148 KB
testcase_27 AC 368 ms
87,240 KB
testcase_28 AC 364 ms
87,264 KB
testcase_29 AC 366 ms
87,392 KB
testcase_30 AC 362 ms
87,244 KB
testcase_31 AC 311 ms
87,200 KB
testcase_32 AC 302 ms
87,204 KB
testcase_33 AC 304 ms
87,252 KB
testcase_34 AC 397 ms
87,404 KB
testcase_35 AC 236 ms
87,264 KB
権限があれば一括ダウンロードができます

ソースコード

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