[UVa 11276] 神奇的七 - cstdio - 88442

记录编号	88442	评测结果	AAAAAAA
题目名称	[UVa 11276] 神奇的七	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	4.218 s
提交时间	2014-02-20 22:21:20	内存使用	0.32 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<cmath>
using namespace std;
//本题下标从0开始
typedef unsigned long long ll;
const int SIZES=130;
const ll MOD=10000;
int getdig(int s,int k){
	return (s>>(k<<1))&3;
}
void printdig(int s){//调试接口,输出s的二进制
	for(int i=0;i<8;i++) cout<<getdig(s,i);
}
int changedig(int s,int k,int t){
	int temp=(k<<1);
	s&=~(3<<temp);
	return s|(t<<temp);
}
vector<int> ham_st;//插头DP(7格)的状态集合
class MATRIX{
public:
	int n,m;
	vector<pair<pair<int,int>,int> > val;
	int fr[SIZES];
	void print(void){//调试接口,输出矩阵
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=0;i<val.size();i++) cout<<val[i].first.first<<" "<<val[i].first.second<<" : "<<val[i].second<<endl;
	}
	void clear(int x,int y){
		n=x,m=y;
		val.clear();
		memset(fr,-1,sizeof(fr));
	}
	void assign_one(int x){
		n=m=x;
		for(int i=0;i<x;i++){
			val.push_back(make_pair(make_pair(i,i),1));
			fr[i]=i;
		}
	}
	void assign_array(ll atp[SIZES][SIZES]){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(atp[i][j]){
					atp[i][j]%=MOD;
					val.push_back(make_pair(make_pair(i,j),atp[i][j]));
					if(fr[i]==-1) fr[i]=val.size()-1;
				}
			}
		}
	}
	int value(int p,int q){
		for(int i=0;i<val.size();i++){
			if(val[i].first.first==p&&val[i].first.second==q) return val[i].second;
		}
		return 0;
	}
};
MATRIX operator * (MATRIX &a,MATRIX &b){
	MATRIX ans;
	ans.clear(a.n,b.m);
	ll atp[SIZES][SIZES]={0};
	int p,q,r,v1,v2;
	for(int i=0;i<a.val.size();i++){
		p=a.val[i].first.first,q=a.val[i].first.second,v1=a.val[i].second;
		for(int j=b.fr[q];j<b.val.size()&&b.val[j].first.first==q;j++){
			r=b.val[j].first.second,v2=b.val[j].second;
			atp[p][r]+=v1*v2;
		}
	}
	ans.assign_array(atp);
	return ans;
}
MATRIX D_DOM,D_HAMMT,D_HAMSM,D_HAMSF;//转移矩阵:多米诺骨牌,多回路,单回路的中间,单回路的最后一列
MATRIX ORI_DOM,ORI_HAMM,ORI_HAMS;//初始矩阵:多米诺骨牌,多回路,单回路
MATRIX quickpow(MATRIX a,ll n){
	MATRIX ans;
	ans.assign_one(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
void DOM_DFS(ll s[SIZES][SIZES],int s1,int s2,int p){
	if(p>7) return;
	if(p==7){
		s[s1][s2]++;
		return;
	}
	DOM_DFS(s,s1*2,s2*2+1,p+1);//这一格不放
	DOM_DFS(s,s1*2+1,s2*2,p+1);//竖着放
	DOM_DFS(s,s1*4+3,s2*4+3,p+2);//横着放
}
int rightmatch(int s,int k){//与s的第k位匹配的右插头
	int dta=1,temp;
	while(k<8){
		k++;
		temp=getdig(s,k);
		if(temp==1) dta++;
		else if(temp==2) dta--;
		if(dta==0) return k;
	}
	cout<<"bracket match error!"<<endl;
	return -1;
}
int leftmatch(int s,int k){
	int dta=-1,temp;
	while(k>=0){
		k--;
		temp=getdig(s,k);
		if(temp==1) dta++;
		else if(temp==2) dta--;
		if(dta==0) return k;
	}
	cout<<"bracket match error!"<<endl;
	return -1;
}
bool plug_exi(int x,int type,int dir){
	//2下4右
	if(dir==2){
		return x<6;
	}
	if(dir==4){
		return (type==0||type==1);
	}
	cout<<"plug check error!";
	return 0;
}
void HAM_DFS(ll s[SIZES][SIZES],int pos,int now,int x,int type){//最开始的那个状态是ham_st[pos],现在到了now,该放第x行
	//type=0:多回路,type=1:单回路的中间,type=2:单回路的最后一列
	if(x==7){
		if(getdig(now,7)==0){
			int nowpos=lower_bound(ham_st.begin(),ham_st.end(),now)-ham_st.begin();
			s[pos][nowpos]++;
			s[pos][nowpos]%=MOD;
		}
		return;
	}
	int p=getdig(now,x),q=getdig(now,x+1),next;
	if(!p&&!q){//两个都是0
		if(plug_exi(x,type,2)&&plug_exi(x,type,4)){//有下插头和右插头
			next=now;
			next=changedig(next,x,1),next=changedig(next,x+1,2);//有下插头和右插头,二者匹配
			HAM_DFS(s,pos,next,x+1,type);
		}
	}
	else if(!(p&&q)&&(p||q)){//一个是0一个不是0
		if(plug_exi(x,type,2)){//下
			next=now;
			next=changedig(next,x,0),next=changedig(next,x+1,p+q);
			HAM_DFS(s,pos,next,x+1,type);
		}
		if(plug_exi(x,type,4)){//右
			next=now;
			next=changedig(next,x,p+q),next=changedig(next,x+1,0);
			HAM_DFS(s,pos,next,x+1,type);
		}
	}
	else if(p==1&&q==1){
		next=changedig(now,rightmatch(now,x+1),1);
		next=changedig(next,x,0),next=changedig(next,x+1,0);
		HAM_DFS(s,pos,next,x+1,type);
	}
	else if(p==2&&q==2){
		next=changedig(now,leftmatch(now,x),2);
		next=changedig(next,x,0),next=changedig(next,x+1,0);
		HAM_DFS(s,pos,next,x+1,type);
	}
	else if(p==2&&q==1){
		next=now;
		next=changedig(next,x,0),next=changedig(next,x+1,0);
		HAM_DFS(s,pos,next,x+1,type);
	}
	else if(p==1&&q==2){
		if(type==0||(type==2&&x==6)){
			next=now;
			next=changedig(next,x,0),next=changedig(next,x+1,0);
			HAM_DFS(s,pos,next,x+1,type);
		}
	}
}
void HAM_prepare(MATRIX &D,int type){
	ll atp[SIZES][SIZES]={0};
	D.clear(ham_st.size(),ham_st.size());
	for(int i=0;i<ham_st.size();i++){
		HAM_DFS(atp,i,ham_st[i]<<2,0,type);
	}
	D.assign_array(atp);
}
void HAM_searchST(int s,int left,int right,int p){
	if(p==7){
		if(left==right) ham_st.push_back(s);
		return;
	}
	HAM_searchST(s<<2,left,right,p+1);//空
	if(left<right) HAM_searchST((s<<2)+1,left+1,right,p+1);//左
	HAM_searchST((s<<2)+2,left,right+1,p+1);//右
}
void prepare(void){
	ll atp[SIZES][SIZES]={0};
	HAM_searchST(0,0,0,0);
	D_DOM.clear(128,128);
	DOM_DFS(atp,0,0,0);
	D_DOM.assign_array(atp);
	HAM_prepare(D_HAMMT,0);
	HAM_prepare(D_HAMSM,1);
	HAM_prepare(D_HAMSF,2);
	memset(atp,0,sizeof(atp));
	ORI_DOM.clear(1,128);
	atp[0][127]=1;
	ORI_DOM.assign_array(atp);
	memset(atp,0,sizeof(atp));
	ORI_HAMM.clear(1,ham_st.size());
	atp[0][0]=1;
	ORI_HAMM.assign_array(atp);
	memset(atp,0,sizeof(atp));
	ORI_HAMS.clear(1,ham_st.size());
	atp[0][0]=1;
	ORI_HAMS.assign_array(atp);
}
void answer(ll n){
	if(n&1){
		printf("0000\n");
		return;
	}
	MATRIX A=ORI_DOM,B=ORI_HAMM,C=ORI_HAMS;
	MATRIX tpa=quickpow(D_DOM,n),tpb=quickpow(D_HAMMT,n),tpc=quickpow(D_HAMSM,n-1);
	A=A*tpa;B=B*tpb;C=C*tpc;C=C*D_HAMSF;
	int ans=0;
	ans+=A.value(0,127),ans+=B.value(0,0),ans+=C.value(0,0);
	ans%=MOD;
	printf("%04d\n",ans);
}
int main(){
	freopen("magicalseven.in","r",stdin);
	freopen("magicalseven.out","w",stdout);
	prepare();
	ll n;
	while(scanf("%llu",&n)!=EOF) answer(n);
	return 0;
}