結果

問題 No.426 往復漸化式
ユーザー Guowen Rong
提出日時 2024-10-15 23:41:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,371 bytes
コンパイル時間 2,393 ms
コンパイル使用メモリ 176,264 KB
実行使用メモリ 113,152 KB
最終ジャッジ日時 2024-10-15 23:41:07
合計ジャッジ時間 7,223 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define _For(i,l,r) for(register int i=r;i>=l;i--)
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e5+10,M=3,mod=1e9+7;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Matrix{
    ll n,m;
    ll a[M][M];
    Matrix(){memset(a,0,sizeof(a));}
    ll* operator[](ll x){
        return a[x];
    }
    void init(ll _n,ll _m,bool f=0){
        n=_n,m=_m;
        if(f){
            For(i,0,n-1)
              a[i][i]=1;
        }
    }
    void Read(){
        For(i,0,n-1)
          For(j,0,m-1)
            a[i][j]=read();
    }
    friend Matrix operator+(Matrix a,Matrix b){
        Matrix ans;
        ans.init(a.n,a.m);
        For(i,0,a.n-1)
          For(j,0,a.m-1)
            ans[i][j]=a[i][j]+b[i][j];
        return ans;
    }
    friend Matrix operator*(Matrix a,Matrix b){ // (3,3),(3,1)
        Matrix ans;
        ans.n=a.n,ans.m=b.m;
        For(i,0,a.n-1)
          For(j,0,b.m-1)
            For(k,0,a.m-1)
              ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;
        return ans;
    }
}A,B,_A,_B,Aans,Bans,BD,AD,SD;
ll n,q,x;
char op[3];
namespace Seg{
    struct Node{
        ll l,r;
        Matrix t1,t2,t3;
    }X[N<<2];
    void pushup(ll k){
        X[k].t1=X[k<<1|1].t1*X[k<<1].t1;
        X[k].t2=X[k<<1].t2*X[k<<1|1].t2;
        X[k].t3=X[k<<1].t3+X[k<<1].t2*X[k<<1|1].t3*X[k<<1].t1;
    }
    void build(ll k,ll l,ll r){
        X[k].l=l,X[k].r=r;
        X[k].t1.init(3,3,1);
        X[k].t2.init(2,2,1);
        X[k].t3.init(2,3);
        if(l==r){
            X[k].t3[0][0]=l*6;
            X[k].t3[0][1]=l*6+1;
            X[k].t3[0][2]=l*6+2;
            X[k].t3[1][0]=l*6+3;
            X[k].t3[1][1]=l*6+4;
            X[k].t3[1][2]=l*6+5;
            return ;
        }
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    void update(ll k,ll i,Matrix v,bool f){
//      cerr<<k<<':'<<X[k].l<<' '<<X[k].r<<'\n';
        if(X[k].l==i&&i==X[k].r){
            if(f)
              X[k].t2=v;
            else
              X[k].t1=v;
            return ;
        }
        ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          update(k<<1,i,v,f);
        else
          update(k<<1|1,i,v,f);
        pushup(k);
    }
    Matrix query1(ll k,ll l,ll r){
//      puts("Yes1");
//      cerr<<k<<':'<<l<<' '<<r<<' '<<X[k].l<<' '<<X[k].r<<'\n';
        if(l>r||l<0)
          return AD;
        if(X[k].l==l&&r==X[k].r)
          return X[k].t1;
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query1(k<<1,l,r);
        else if(l>mid)
          return query1(k<<1|1,l,r);
        else
          return query1(k<<1|1,mid+1,r)*query1(k<<1,l,mid);
    }
    Node query3(ll k,ll l,ll r){
//      puts("Yes3");
        if(l>r||r>n)
          return {0,0,AD,BD,SD};
        if(X[k].l==l&&r==X[k].r)
          return X[k];
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query3(k<<1,l,r);
        else if(l>mid)
          return query3(k<<1|1,l,r);
        else{
            Node ans;
            auto L=query3(k<<1,l,mid),R=query3(k<<1|1,mid+1,r);
            ans.t1=R.t1*L.t1;
            ans.t2=L.t2*R.t2;
            ans.t3=L.t3+L.t2*R.t3*L.t1;
            return ans;
        }
    }
};
bool End;
int main(){
//  open("A.in","A.out");
    AD.init(3,3,1),BD.init(2,2,1),SD.init(2,3,1);
    n=read();
    A.init(3,1),Aans.init(3,1),_A.init(3,3);
    A.Read();
    B.init(2,1),Bans.init(2,1),_B.init(2,2);
    B.Read();
    Seg::build(1,0,n);
    q=read();
    while(q--){
        scanf("%s",op);
        if(op[1]=='a'){
            x=read()-1;
            if(x<0)
              Aans=A;
            else
              Aans=Seg::query1(1,0,x)*A;
            write(Aans[0][0]);
            putchar(' ');
            write(Aans[1][0]);
            putchar(' ');
            write(Aans[2][0]);
            putchar('\n');          
        }
        else if(op[1]=='b'){
            x=read();
            if(x==n)
              Bans=B;
            else{
                auto X=Seg::query3(1,x+1,n);
                auto Y=Seg::query1(1,0,x)*A;
                Bans=(X.t3*Y)+(X.t2*B);
            }
            write(Bans[0][0]);
            putchar(' ');
            write(Bans[1][0]);
            putchar('\n');
        }
        else if(op[0]=='a'){
            x=read();
            _A.Read();
            Seg::update(1,x,_A,0);      
        }
        else{
            x=read();
            _B.Read();
//          cerr<<x<<'\n';
            Seg::update(1,x,_B,1);
        }
    }
    cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0