結果

問題 No.426 往復漸化式
ユーザー btkbtk
提出日時 2016-09-23 00:16:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 5,000 ms
コード長 5,557 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 178,740 KB
実行使用メモリ 44,524 KB
最終ジャッジ日時 2024-11-17 15:33:00
合計ジャッジ時間 4,668 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;


typedef long long LL;

template<typename T>void chmin(T &a,T b){a=min(a,b);}
template<typename T>void chmax(T &a,T b){a=max(a,b);}
template<typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

const LL MOD = 1e9+7;
#define SIZE 400000
#define L(v) (v*2+1)
#define R(v) (v*2+2)

struct A{
    LL v[3][3];
};
struct B{
    LL v[2][2];
};
struct C{
    LL v[2][3];
};

#define mm(res,x,y,z)  for(int i=0;i<x;i++)for(int j=0;j<y;j++){res.v[i][j]=0;for(int k=0;k<z;k++)(res.v[i][j]+=l.v[i][k]*r.v[k][j])%=MOD;}
A mulmat(A l,A r){
    A res;
    mm(res,3,3,3);
    return res;
}

B mulmat(B l,B r){
    B res;
    mm(res,2,2,2);
    return res;
}
C mulmat(B l,C r){
    C res;
    mm(res,2,3,2);
    return res;
}
C mulmat(C l,A r){
    C res;
    mm(res,2,3,3);
    return res;
}
C mulmat(B b,C c,A a){
    return mulmat(mulmat(b,c),a);
}
C addmat(C l,C r){
    C res;
    for(int i=0;i<2;i++)
        for(int j=0;j<3;j++){
            res.v[i][j]=l.v[i][j]+r.v[i][j];
            if(res.v[i][j]>=MOD)res.v[i][j]-=MOD;
        }
    return res;
}
struct val{
    A a;
    B b;
    C c;
};
val getinitval(){
    val res;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)res.a.v[i][j]=0;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)res.b.v[i][j]=0;
    for(int i=0;i<2;i++)for(int j=0;j<3;j++)res.c.v[i][j]=0;
    for(int i=0;i<3;i++)res.a.v[i][i]=1;
    for(int i=0;i<2;i++)res.b.v[i][i]=1;
    return res;
}
struct node {
    int bg, ed;
    val v;
    int len() { return ed - bg + 1; };
    inline val getval() {return v;}
    inline void init(int b, int e) {
        bg = b, ed = e;
    }
    bool isleaf() { return bg == ed; }
}mem[SIZE];

inline val combine(val l, val r) {
    return val{
        mulmat(r.a,l.a),
            mulmat(l.b,r.b),
            addmat(l.c,mulmat(l.b,r.c,l.a))
            };
}

class segT {
private:
    node *t;
public:
    segT(int bg, int ed) :t(mem) { make_tree(bg, ed); }

    void update(int v) {
        node *p = t + v, *l = t + L(v), *r = t + R(v);
        if (!p->isleaf())
            p->v = combine(l->getval(), r->getval());
    }
    void set_A(int pos,A& x,int v = 0) {
        node *p = t + v, *l = t + L(v), *r = t + R(v);
        if (pos == p->bg&&pos == p->ed) {
            p->v.a=x;
            return;
        }
        if (pos <=min(pos, l->ed))
            set_A(pos, x, L(v));
        else
            set_A(pos, x, R(v));
        update(v);
    }
    void set_B(int pos,B& x,int v = 0) {
        node *p = t + v, *l = t + L(v), *r = t + R(v);
        if (pos == p->bg&&pos == p->ed) {
            p->v.b=x;
            return;
        }
        if (pos <=min(pos, l->ed))
            set_B(pos, x, L(v));
        else
            set_B(pos, x, R(v));
        update(v);
    }

    val get(int bg,int ed, int v = 0) {
        node *p = t + v, *l = t + L(v), *r = t + R(v);
        if (bg == p->bg&&ed == p->ed) {
            return p->getval();
        }
        int m;
        val res=getinitval();
        if (bg <= (m = min(ed, l->ed)))
            res=combine(res,get(bg, m, L(v)));
        if ((m = max(bg, r->bg)) <= ed)
            res=combine(res,get(m, ed, R(v)));
        return res;
    }
    void make_tree(int bg, int ed, int v = 0) {
        //cout<<bg<<" "<<ed<<endl;
        node *p = t + v;
        p->init(bg, ed);
        if (!p->isleaf()) {
            int m = (bg + ed) / 2;
            make_tree(bg, m, L(v));
            make_tree(m+1, ed, R(v));
            update(v);
        }
        else{
            p->v=getinitval();
            for(int j=0;j<2;j++)
                for(int k=0;k<3;k++)
                    p->v.c.v[j][k]=6*bg+j*3+k;

        }
    }
};

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
        
}}init;
LL a0[3];
LL bn[2];
LL ai[3];
LL bi[2];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<3;i++)cin>>a0[i];
    for(int i=0;i<2;i++)cin>>bn[i];

    segT tree(0,n);
    int q;
    cin>>q;
    while(q--){
        string s;int i;
        cin>>s>>i;
        if(s=="a"){
            A v;
            for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>v.v[i][j];
            tree.set_A(i,v);
        }
        else if(s=="b"){
            B v;
            for(int i=0;i<2;i++)for(int j=0;j<2;j++)cin>>v.v[i][j];
            tree.set_B(i,v);
        }
        else if(s=="ga"){
            if(i==0){
                cout<<a0[0]<<" "<<a0[1]<<" "<<a0[2]<<endl;
            }
            else{
                val v= tree.get(0,i-1);
                for(int i=0;i<3;i++){
                    ai[i]=0;
                    for(int j=0;j<3;j++)
                        (ai[i]+=v.a.v[i][j]*a0[j])%=MOD;
                }
                cout<<ai[0]<<" "<<ai[1]<<" "<<ai[2]<<endl;
            }
        }
        else if(s=="gb"){
            if(i==n){
                cout<<bn[0]<<" "<<bn[1]<<endl;
            }else{
                val v= tree.get(0,i);
                for(int i=0;i<3;i++){
                    ai[i]=0;
                    for(int j=0;j<3;j++)
                        (ai[i]+=v.a.v[i][j]*a0[j])%=MOD;
                }
                v=tree.get(i+1,n);
                for(int i=0;i<2;i++){
                    bi[i]=0;
                    for(int j=0;j<2;j++)
                        (bi[i]+=v.b.v[i][j]*bn[j])%=MOD;
                    for(int j=0;j<3;j++)
                        (bi[i]+=v.c.v[i][j]*ai[j])%=MOD; 
                }
                cout<<bi[0]<<" "<<bi[1]<<endl;             
            }
        }
    }
    return 0;
}
0