結果

問題 No.510 二次漸化式
ユーザー imulanimulan
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 113 ms
5,376 KB
testcase_03 AC 113 ms
5,376 KB
testcase_04 AC 113 ms
5,376 KB
testcase_05 AC 113 ms
5,376 KB
testcase_06 AC 202 ms
13,824 KB
testcase_07 AC 198 ms
13,952 KB
testcase_08 AC 201 ms
13,824 KB
testcase_09 AC 198 ms
13,824 KB
testcase_10 AC 43 ms
5,376 KB
testcase_11 AC 43 ms
5,376 KB
testcase_12 AC 42 ms
5,376 KB
testcase_13 AC 42 ms
5,376 KB
testcase_14 AC 43 ms
5,376 KB
testcase_15 AC 42 ms
5,376 KB
testcase_16 AC 253 ms
87,368 KB
testcase_17 AC 250 ms
87,352 KB
testcase_18 AC 248 ms
87,424 KB
testcase_19 AC 248 ms
87,304 KB
testcase_20 AC 251 ms
87,252 KB
testcase_21 AC 249 ms
87,268 KB
testcase_22 AC 251 ms
87,284 KB
testcase_23 AC 384 ms
87,284 KB
testcase_24 AC 387 ms
87,296 KB
testcase_25 AC 384 ms
87,272 KB
testcase_26 AC 389 ms
87,332 KB
testcase_27 AC 384 ms
87,396 KB
testcase_28 AC 383 ms
87,276 KB
testcase_29 AC 381 ms
87,296 KB
testcase_30 AC 387 ms
87,296 KB
testcase_31 AC 332 ms
87,424 KB
testcase_32 AC 320 ms
87,364 KB
testcase_33 AC 327 ms
87,384 KB
testcase_34 AC 402 ms
87,400 KB
testcase_35 AC 241 ms
87,336 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