leetcode 552

a.cpp

class Solution {
	const int M=1000000007;
	
template<class T>
class mx{
public:
	int H,W;
	vector<T> v;
	mx(const mx<T> &rhs):W(rhs.W),H(rhs.H){
		v=rhs.v;
	}
	mx(int h,int w):W(w),H(h){
		v.resize(h*w);
	}
	mx(int h,int w,const vector<T> &val):W(w),H(h){
		v.resize(h*w);
		setVal(val);
	}
	mx(int h,int w,const vector<T> &val,const T &pad):W(w),H(h){
		v.resize(h*w);
		setVal(val,pad);
	}
	void setVal(const vector<T> &val){
		for(int x=0,xs=min(v.size(),val.size());x!=xs;++x) v[x]=val[x];
	}
	void setVal(const vector<T> &val,const T &pad){
		int x=0; for(int xs=min(v.size(),val.size());x!=xs;++x) v[x]=val[x];
		if(val.size()<v.size()) for(int xs=v.size();x!=xs;++x) v[x]=pad;
	}
	mx<T> &operator*=(const mx<T> &rhs){
		vector<T> tmp(H*rhs.W);
		for(int y=0;y!=H;++y){
			for(int x=0;x!=rhs.W;++x){
				tmp[y*W+x]=v[y*W]*rhs.v[x];
				for(int k=1;k!=W;++k){
					tmp[y*W+x]+=v[y*W+k]*rhs.v[k*rhs.W+x];
				}
			}
		}
		v=std::move(tmp);
		W=rhs.W;
		return *this;
	}
	mx<T> operator*(const mx<T> &rhs)const{
		mx<T> rtv(*this);
		return rtv*=rhs;
	}
	void mul_M(const mx<T> &rhs,const int MOD){
		vector<T> tmp(H*rhs.W);
		for(int y=0;y!=H;++y){
			for(int x=0;x!=rhs.W;++x){
				tmp[y*W+x]=v[y*W]*rhs.v[x];
				for(int k=1;k!=W;++k){
					tmp[y*W+x]+=v[y*W+k]*rhs.v[k*rhs.W+x];
					tmp[y*W+x]%=MOD;
				}
			}
		}
		v=std::move(tmp);
		W=rhs.W;
	}
};

public:
	int checkRecord(int n) {
		/*
		int tbl1[6],tbl2[6];
		int *tbl=tbl1,*dst=tbl2;
		for(int x=0;x!=6;++x){
			tbl[x]=x<3;
		}
		*/
		/*
		L0
		L0A
		L1
		L1A
		L2
		L2A
		*/
		/*
		for(int x=6,xs=n*6,tmp,tmpA;x!=xs;x+=6){
			// L -> +2
			tmpA=tmp=0;
			for(int z=0;z!=4;z+=2){
				tmp+=(dst[z+2]=tbl[z]);
				tmp%=M;
				tmpA+=(dst[(z|1)+2]=tbl[(z|1)]);
				tmpA%=M;
			}
			// P -> 0,1
			tmp+=tbl[4];
			tmp%=M;
			tmpA+=tbl[5];
			tmpA%=M;
			dst[0]=tmp;
			// A -> 1
			dst[1]=(tmp+tmpA)%M;
			swap(tbl,dst);
		}
		*/
		mx<long long int> b(6,6,{
			1,0,1,0,1,0,
			1,1,1,1,1,1,
			1,0,0,0,0,0,
			0,1,0,0,0,0,
			0,0,1,0,0,0,
			0,0,0,1,0,0,
		}),r(6,6,{
			1,0,0,0,0,0,
			0,1,0,0,0,0,
			0,0,1,0,0,0,
			0,0,0,1,0,0,
			0,0,0,0,1,0,
			0,0,0,0,0,1,
		}),d1(6,1,{
			1,
			1,
			1,
			0,
			0,
			0,
		}),s(1,6,{
			1,1,1,1,1,1,
		});
		for(--n;n;n>>=1){
			if(n&1) r.mul_M(b,M);
			b.mul_M(b,M);
		}
		s.mul_M(r,M);
		s.mul_M(d1,M);
		return s.v[0];
	}
};