#include // c #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; #define ALL(c) (begin(c)),(end(c)) #define REP(i,n) FOR(i,0,n) #define REPr(i,n) FORr(i,0,n) #define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i) #define FORr(i,l,r) for(int i=(int)(r)-1;i>=(int)(l);--i) #define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it) #define IN(l,v,r) ((l)<=(v) && (v)<(r)) #define UNIQUE(v) v.erase(unique(ALL(v)),v.end()) //debug #define DUMP(x) cerr << #x << " = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" class range { private: struct Iter{ int v; int operator*(){return v;} bool operator!=(Iter& itr) {return v < itr.v;} void operator++() {++v;} }; Iter i, n; public: range(int n) : i({0}), n({n}) {} range(int i, int n) : i({i}), n({n}) {} Iter& begin() {return i;} Iter& end() {return n;} }; //input template istream& operator >> (istream& is,pair& p){is>>p.first>>p.second;return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t) >> get<1>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >>get<0>(t)>>get<1>(t)>>get<2>(t);return is;} template istream& operator >> (istream& is,tuple& t){is >> get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t);return is;} template istream& operator >> (istream& is, const tuple& t){is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return is;} template istream& operator >> (istream& is,vector& as){REP(i,as.size())is >>as[i];return is;} //output template ostream& operator << (ostream& os, const set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< ostream& operator << (ostream& os, const pair& p){os< ostream& operator << (ostream& os, const map& m){bool isF=true;for(auto& p:m){if(!isF)os< ostream& operator << (ostream& os, const tuple& t){os << get<0>(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const tuple& t){os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template ostream& operator << (ostream& os, const vector& as){REP(i,as.size()){if(i!=0)os<<" "; os< ostream& operator << (ostream& os, const vector>& as){REP(i,as.size()){if(i!=0)os< T INF(){assert(false);}; template<> int INF(){return 1<<28;}; template<> ll INF(){return 1LL<<58;}; template<> double INF(){return 1e16;}; template<> long double INF(){return 1e16;}; template T EPS(){assert(false);}; template<> int EPS(){return 1;}; template<> ll EPS(){return 1LL;}; template<> double EPS(){return 1e-8;}; template<> long double EPS(){return 1e-8;}; template T pmod(T v,U M){return (v%M+M)%M;} template class Monoid{ public: virtual T e()=0,c(T,T)=0; }; template using CommutativeMonoid = Monoid; template class SemiRing:public virtual CommutativeMonoid{ public: virtual T me()=0,mc(T,T)=0; }; template class Group:public virtual Monoid{ public: virtual T inv(T)=0; }; template using CommutativeGroup = Group; template class Ring:public virtual Group,public virtual SemiRing{ public: }; template class ZRing:public Ring{ public: T e(){return 0;} T c(T a,T b){return a+b;} T inv(T a){return -a;} T me(){return 1;} T mc(T a,T b){return a*b;} static ZRing& i(){static ZRing i;return i;} }; template int sig(D a,D b=0){return a()?-1:a>b+EPS()?1:0;} namespace Matrix{ class Inconsistent{};//none class Ambiguous{};//many class NoSolution{}; template class Mat :public vector>{ public: const int H,W;Ring& f; Mat(int H,int W,Ring& f) : vector>(H,vector(W,f.e())),H(H),W(W),f(f){} inline Mat e(){ return vector>(H,vector(W,f.e())); } inline Mat c(Mat a,Mat b){return a+b;} inline Mat inv(Mat a){return -a;} const inline Mat me(){ static Mat A(H,W); for(int y:range(H))for(int x:range(W))A[y][x]=f.e(); for(int i:range(min(H,W)))A[i][i]=f.me(); return A; } inline Mat mc(Mat a,Mat b){return a*b;} //O(n^2) Mat operator+(const Mat& r){ const Mat& l=*this; Mat res(l.H,r.W); for(int y:range(l.H))for(int x:range(r.W)) res[y][x]=f.c(l[y][x],r[y][x]); return res; } //O(n^2) Mat operator-(){ Mat res=*this; for(int y:range(res.H))for(int x:range(res.W)) res[y][x]=f.inv(res[y][x]); return res; } Mat operator-(const Mat& r){ return (*this) + (-r); } //O(n^3) Mat operator*(const Mat& r){ const Mat& l=*this; Mat res(l.H,r.W); for(int y:range(l.H))for(int x:range(r.W))for(int k:range(r.H)) res[y][x]=f.c(res[y][x],f.mc(l[y][k],r[k][x])); return res; } //O(n^2) vector operator*(const vector& r){ const Mat& l=*this; vector res(r.size()); for(int y:range(l.H))for(int x:range(l.W))res[y]=f.c(res[y],f.mc(l[y][x],r[x])); return res; } // O(n^3*log(d)) // Mat x must be n*n size //:TODO abstraction Mat pow(ll d){ Mat x=*this,res=e(); while(d!=0){ if(d%2)res=res*x; x=x*x; d/=2; } return res; } // //連立方程式 // const int gf=2; // T mod(T v){return mod(v,gf);} // T inv(T v){return invs[v];} //O(n^3) //Ax = b void gauss(vector& b){ Mat A=*this; const int H = A.H,W=A.W; int py =0,px = 0; while(py < H && px < W){ for(int y=py+1;y0){ swap(A[y],A[py]);swap(b[y],b[py]); } } if(sig(A[py][px]) != 0){ T d = 1/A[py][px]; for(int x=0;x=0;x--)for(int y=0;y> N; Mat mat(max(N+1,2),max(N+1,2),ZRing::i()); vector bs(max(N+1,2));bs[0]=4;bs[1]=3; mat[0][0]=1; mat[1][1]=1; for(int k=2;k<=N;k++){ mat[k][k]=-4; mat[k][k-1]=19; mat[k][k-2]=-12; } mat.gauss(bs); cout << bs[N]<