結果
| 問題 | No.426 往復漸化式 |
| ユーザー |
 sigma425
|
| 提出日時 | 2017-09-14 22:39:14 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 1,327 ms / 5,000 ms |
| コード長 | 6,518 bytes |
| コンパイル時間 | 3,129 ms |
| コンパイル使用メモリ | 211,880 KB |
| 実行使用メモリ | 284,124 KB |
| 最終ジャッジ日時 | 2024-11-07 20:09:18 |
| 合計ジャッジ時間 | 22,216 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
/*あのさぁ・・・*/#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)#define rep1(i,n) for(int i=1;i<=(int)(n);i++)#define all(c) c.begin(),c.end()#define pb push_back#define fs first#define sc second#define show(x) cout << #x << " = " << x << endl#define chmin(x,y) x=min(x,y)#define chmax(x,y) x=max(x,y)using namespace std;template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}template<unsigned int mod_>struct ModInt{using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr static uint mod = mod_;uint v;ModInt():v(0){}ModInt(ll v):v(normS(v%mod+mod)){}explicit operator bool() const {return v!=0;}static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1]static ModInt make(const uint &x){ModInt m; m.v=x; return m;}ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}ModInt operator-() const { return make(normS(mod-v)); }ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}ModInt operator/(const ModInt& b) const { return *this*b.inv();}ModInt& operator+=(const ModInt& b){ return *this=*this+b;}ModInt& operator-=(const ModInt& b){ return *this=*this-b;}ModInt& operator*=(const ModInt& b){ return *this=*this*b;}ModInt& operator/=(const ModInt& b){ return *this=*this/b;}ll extgcd(ll a,ll b,ll &x,ll &y) const{ll u[]={a,1,0},v[]={b,0,1};while(*v){ll t=*u/ *v;rep(i,3) swap(u[i]-=t*v[i],v[i]);}if(u[0]<0) rep(i,3) u[i]=-u[i];x=u[1],y=u[2];return u[0];}ModInt inv() const{ll x,y;extgcd(v,mod,x,y);return make(normS(x+mod));}bool operator==(const ModInt& b) const { return v==b.v;}bool operator!=(const ModInt& b) const { return v!=b.v;}friend istream& operator>>(istream &o,ModInt& x){ll tmp;o>>tmp;x=ModInt(tmp);return o;}friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}};using mint = ModInt<1000000007>;template<class T>struct Matrix{int H,W;vector< vector<T> > m;Matrix():H(0),W(0){}Matrix(int H,int W):H(H),W(W),m( vector< vector<T> >(H,vector<T>(W,0)) ){}vector<T> const& operator[](const int& i) const {return m[i];}vector<T>& operator[](const int& i) {return m[i];}Matrix operator+=(const Matrix& b){assert(H==b.H&&W==b.W);rep(i,H) rep(j,W) m[i][j]+=b[i][j];return *this;}Matrix operator-=(const Matrix& b){assert(H==b.H&&W==b.W);rep(i,H) rep(j,H) m[i][j]-=b[i][j];return *this;}Matrix operator+(const Matrix& b) const {return Matrix(*this)+=b;}Matrix operator-(const Matrix& b) const {return Matrix(*this)-=b;}Matrix operator*(const Matrix& b) const {assert(W==b.H);Matrix c(H,b.W);rep(i,H) rep(j,b.W) rep(k,W) c[i][j]+=m[i][k]*b[k][j];return c;}Matrix operator*=(const Matrix& b){return (*this)=(*this)*b;}vector<T> operator*(const vector<T>& b) const {assert(W==b.size());vector<T> c(H);rep(i,H) rep(j,W) c[i]+=m[i][j]*b[j];return c;}static Matrix E(int N){Matrix a(N,N);rep(i,N) a[i][i]=1;return a;}friend ostream& operator<<(ostream &o,const Matrix& m){o<<m.H<<" * "<<m.W<<endl;rep(i,m.H){o<<"[";rep(j,m.W) o<<m[i][j]<<" ";o<<"]"<<endl;}return o;}};template<class D>struct segtree_simple{int N;vector<D> val;segtree_simple(){}segtree_simple(int n){N=1;while(N<n) N*=2;val.assign(N*2,D::e());}segtree_simple(const vector<D>& ds){int n = ds.size();N=1;while(N<n) N*=2;val.assign(N*2,D::e());rep(i,n) val[i+N] = ds[i];for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];}void assign(int k,D d){k+=N;val[k]=d;k/=2;while(k){val[k] = val[k*2] + val[k*2+1];k/=2;}}D query(int a,int b){ //non-commutative & unrecursiveD L = D::e() , R = D::e();a+=N,b+=N;while(a<b){if(a&1) L = L + val[a++];if(b&1) R = val[--b] + R;a/=2,b/=2;}return L+R;}};struct MA{static const int N = 3;Matrix<mint> a;MA(){}MA(Matrix<mint> a):a(a){}const static MA e(){return Matrix<mint>::E(N);}MA operator+(const MA& r) const {return MA(r.a*a);};};struct MB{static const int N = 2;Matrix<mint> a;MB(){}MB(Matrix<mint> a):a(a){}const static MB e(){return Matrix<mint>::E(N);}MB operator+(const MB& r) const {return MB(a*r.a);};};struct D{ //? -> b?a + xusing Mat = Matrix<mint>;Mat b,a,x;D(){*this = e();}D(Mat b,Mat a,Mat x):b(b),a(a),x(x){}const static D e(){return D(Mat::E(2),Mat::E(3),Mat(2,3));}D operator+(const D& r) const {// puts("plus");// show(b);// show(r.x);// show(b*r.x);auto ret = D(b*r.b,r.a*a,b*r.x*a+x);// puts("done");return ret;};};Matrix<mint> X(int x){Matrix<mint> res(2,3);rep(i,2) rep(j,3) res[i][j] = mint(6*x+i*3+j);return res;}segtree_simple<MA> sega;segtree_simple<MB> segb;segtree_simple<D> segd;int main(){int N;cin>>N;vector<mint> a0,bn;rep(i,3){int x;cin>>x;a0.pb(mint(x));}rep(i,2){int x;cin>>x;bn.pb(mint(x));}sega = segtree_simple<MA>(N+1);segb = segtree_simple<MB>(N+1);segd = [&]{vector<D> vs;rep1(i,N+1){D v;v.x = X(i);vs.pb(v);}return segtree_simple<D>(vs);}();int Q;cin>>Q;rep(qt,Q){string s;cin>>s;if(s == "a"){int i;cin>>i;Matrix<mint> x(3,3);rep(i,3) rep(j,3){int v;cin>>v;x.m[i][j] = mint(v);}MA A(x);sega.assign(i,A);MB B = segb.query(i,i+1);D v(B.a,A.a,B.a*X(i+1)*A.a);segd.assign(i,v);}if(s == "b"){int i;cin>>i;Matrix<mint> x(2,2);rep(i,2) rep(j,2){int v;cin>>v;x.m[i][j] = mint(v);}MB B(x);segb.assign(i,B);MA A = sega.query(i,i+1);D v(B.a,A.a,B.a*X(i+1)*A.a);segd.assign(i,v);}if(s == "ga"){int i;cin>>i;auto v = sega.query(0,i).a * a0;cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;}if(s == "gb"){int i;cin>>i;if(i == N){cout<<bn[0]<<" "<<bn[1]<<endl;continue;}auto x = segd.query(i+1,N).x;x += X(i+1);auto v = x * sega.query(0,i+1).a * a0;auto u = segb.query(i+1,N+1).a * bn;cout<<v[0]+u[0]<<" "<<v[1]+u[1]<<endl;}}}