結果
問題 | No.426 往復漸化式 |
ユーザー | sigma425 |
提出日時 | 2017-09-14 22:39:14 |
言語 | C++11 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 4 ms
5,248 KB |
testcase_02 | AC | 4 ms
5,248 KB |
testcase_03 | AC | 25 ms
5,504 KB |
testcase_04 | AC | 24 ms
5,504 KB |
testcase_05 | AC | 214 ms
37,080 KB |
testcase_06 | AC | 216 ms
36,948 KB |
testcase_07 | AC | 944 ms
284,116 KB |
testcase_08 | AC | 937 ms
284,120 KB |
testcase_09 | AC | 1,141 ms
284,124 KB |
testcase_10 | AC | 1,133 ms
283,992 KB |
testcase_11 | AC | 899 ms
284,116 KB |
testcase_12 | AC | 1,052 ms
283,988 KB |
testcase_13 | AC | 1,213 ms
283,996 KB |
testcase_14 | AC | 1,040 ms
284,120 KB |
testcase_15 | AC | 905 ms
284,120 KB |
testcase_16 | AC | 1,071 ms
283,992 KB |
testcase_17 | AC | 1,075 ms
284,124 KB |
testcase_18 | AC | 1,049 ms
284,120 KB |
testcase_19 | AC | 868 ms
283,996 KB |
testcase_20 | AC | 1,008 ms
283,988 KB |
testcase_21 | AC | 1,327 ms
284,116 KB |
testcase_22 | AC | 1,008 ms
283,988 KB |
ソースコード
/* あのさぁ・・・ */ #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 & unrecursive D 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 + x using 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; } } }