记录编号	387044	评测结果	AAAAAAA
题目名称	[UVa 11276] 神奇的七	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	12.982 s
提交时间	2017-03-25 15:42:11	内存使用	85.73 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef unsigned long long ull;
const int N=330;
ull n;
int q[N],tag[1<<16],size;
typedef pair<int,int> pr;
struct matrix{
	int a[N][N];
	vector<pr> E;
	matrix(){clear();}
	void clear(){
		memset(a,0,sizeof a);
		E.clear();
	}
	void set(int x,int y,int val){
		E.push_back(pr(x,y));
		a[x][y]=val;
	}
	void operator *= (const matrix &x){
		static matrix Ans;
		Ans.clear();
		static ull ans[N][N]={0};
		for (int i=E.size()-1;i>=0;i--){
			int X=E[i].first,Y=E[i].second,val=a[X][Y];
			for (int k=0;k<N;k++) ans[X][k]+=val*x.a[Y][k];
		}
		for (int i=0;i<N;i++)
		for (int j=0;j<N;j++)
		if (ans[i][j]){
			Ans.set(i,j,ans[i][j]%10000);
			ans[i][j]=0;
		}
		*this=Ans;
	}
}x1,x2,x3,a1,a2,a3,E,now,ans;
matrix p[3][64];
void mi(int tp,ull y){
	for (int i=0;i<64;i++)
		if (y>>i&1) ans*=p[tp][i];
}
void dfs1(int p,int S,int now){//完美匹配 
	if (p==7){
		x1.set(S,now,1);
		return;
	}
	if (S>>p&1) dfs1(p+1,S,now);
	else{
		dfs1(p+1,S,now|(1<<p));//向后匹配 
		if (p<6&&!(S>>(p+1)&1)) dfs1(p+2,S,now);//向上匹配 
	}
}
void set(int &x,int p,int tp){
	x&=~(3<<(p<<1));
	x|=(tp<<(p<<1));
}
int get(int x,int p){return (x>>(p<<1))&3;}
int stack[N],top,d[N][N];
void dfs(int p,int S,int cnt){
	if (cnt<0) return;
	if (p>7){
		if (cnt) return;
		for (int i=0;i<8;i++){
			int tp=get(S,i);
			if (tp==1) stack[++top]=i;
			if (tp==2){
				d[size][i]=stack[top];
				d[size][stack[top--]]=i;
			}
		}
		q[size++]=S;
		tag[S]=size-1;
		return;
	}
	set(S,p,0);dfs(p+1,S,cnt);
	set(S,p,1);dfs(p+1,S,cnt+1);
	set(S,p,2);dfs(p+1,S,cnt-1);
}
void work(int j,bool TP){//TP=0表示哈密顿圈,TP=1表示生成子图 
	now.clear();
	for (int k=0;k<size;k++){
		int S=q[k],right=get(S,j),down=get(S,j+1);
		if (!right&&!down){
			set(S,j,1);set(S,j+1,2);
			now.set(k,tag[S],1);
		}
		else if (right==1&&down==2){
			if (TP){
				set(S,j,0);set(S,j+1,0);
				now.set(k,tag[S],1);
			}
		}
		else if ((!right)^(!down)){
			int p=right|down;
			set(S,j,p);set(S,j+1,0);now.set(k,tag[S],1);
			set(S,j,0);set(S,j+1,p);now.set(k,tag[S],1);
		}
		else{
			int l=d[k][j],r=d[k][j+1];
			if (l>r) swap(l,r);
			set(S,l,1);set(S,r,2);
			set(S,j,0);set(S,j+1,0);
			now.set(k,tag[S],1);
		}
	}
}
void pushdown(){
	now.clear();
	for (int k=0;k<size;k++){
		int S=q[k];
		if (!get(S,7)) now.set(k,tag[S<<2],1);
	}
}
void init(){
	//完美匹配初始化 
	for (int i=0;i<128;i++) dfs1(0,i,0);
	a1.set(0,0,1);
	//插头dp初始化 
	dfs(0,0,0);
	for (int i=0;i<size;i++) E.set(i,i,1);
	//哈密顿圈初始化 
	a2.set(0,0,1);
	for (int i=0;i<6;i++) work(i,0),a2*=now;
	x2=E;
	work(6,0);x2*=now;
	pushdown();x2*=now;
	for (int i=0;i<6;i++) work(i,0),x2*=now;
	//生成子图初始化 
	x3=E;
	for (int i=0;i<7;i++) work(i,1),x3*=now;
	pushdown();x3*=now;
	a3.set(0,0,1);
	//生成矩阵的幂 
	p[0][0]=x1;p[1][0]=x2;p[2][0]=x3;
	for (int i=1;i<64;i++)
	for (int j=0;j<3;j++)
		p[j][i]=p[j][i-1],p[j][i]*=p[j][i];
}
int main()
{
	freopen("magicalseven.in","r",stdin);
	freopen("magicalseven.out","w",stdout);
	init();
	int end=0;
	set(end,6,1);set(end,7,2);
	while (cin>>n){
		int Ans=0;
		ans=a1;mi(0,n);
		Ans+=ans.a[0][0];
		ans=a2;mi(1,n-1);
		Ans+=ans.a[0][tag[end]];
		if (n>1){
			ans=a3;mi(2,n);
			Ans+=ans.a[0][tag[0]];
		}
		printf("%04d\n",Ans%10000);
	}
	return 0;
}