记录编号	383755	评测结果	AAAAAAA
题目名称	漫游小镇	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-03-16 13:13:15	内存使用	16.90 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,m,q[N],size,d[N][11],tag[1<<22];
ll dp[2][N];
void set(int &x,int p,int tp){
	x&=~(3<<(p<<1));
	x|=(tp<<(p<<1));
}
int Set(int x,int p,int tp){
	set(x,p,tp);
	return x;
}
int Get(int x,int p){return (x>>(p<<1))&3;}
/*void print(int x,int radix=4){
	char s[30]="";
	itoa(x,s,radix);
	printf("%s",s);
}*/
int stack[11],top;
void dfs(int p,int S,int cnt){
	if (cnt<0) return;
	if (p>n){
		if (cnt) return;
		top=0;
		for (int i=0;i<=n;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;
			}
		}
		tag[S]=size;
		q[size++]=S;
		return;
	}
	dfs(p+1,Set(S,p,0),cnt);
	dfs(p+1,Set(S,p,1),cnt+1);
	dfs(p+1,Set(S,p,2),cnt-1);
	dfs(p+1,Set(S,p,3),cnt);
}
int main()
{
	freopen("betsy.in","r",stdin);
	freopen("betsy.out","w",stdout);
	scanf("%d",&n);
	dfs(0,0,0);
	ll *x=dp[0],*y=dp[1],ans=0;
	x[tag[Set(Set(0,n,2),0,1)]]=1;
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			for (int k=0;k<size;k++) y[k]=0;
			for (int k=0;k<size;k++)
			if (x[k]){//现在在(i,j),插头状态为k 
				int S=q[k];
				int right=Get(S,j),down=Get(S,j+1);
				if (right==1&&down==2){
					if (i==n-1&&j==n-1&&!Set(Set(S,j,0),j+1,0)) ans=x[k];
					continue;
				}
				if (right==3&&down==3) continue;
				if (!right&&!down){
					y[tag[Set(Set(S,j,1),j+1,2)]]+=x[k];
					//y[tag[S]]+=x[k];
				}
				else
				if ((!right)^(!down)){
					int p=right|down;
					y[tag[Set(Set(S,j,p),j+1,0)]]+=x[k];
					y[tag[Set(Set(S,j,0),j+1,p)]]+=x[k];
				}
				else
				if (right==3||down==3){
					int T=S;
					set(T,down==3?d[k][j]:d[k][j+1],3);
					set(T,j,0);set(T,j+1,0);
					y[tag[T]]+=x[k];
				}
				else{
					int T=S,l=d[k][j],r=d[k][j+1];
					if (l>r) swap(l,r);
					set(T,l,1),set(T,r,2);
					set(T,j,0),set(T,j+1,0);
					y[tag[T]]+=x[k];
				}
			}
			swap(x,y);
		}
		for (int k=0;k<size;k++) y[k]=0;
		//printf("line:%d\n",i);
		for (int k=0;k<size;k++){
			int S=q[k],tp=Get(S,n);
			if (!tp&&(S<<2)&&x[k])
				y[tag[S<<2]]=x[k];//,print(S),printf(" %lld\n",x[k]);
		}
		//puts("");
		swap(x,y);
	}
	printf("%lld\n",ans);
	return 0;
}