[ASDFZ]老魔杖

Description

有长度为\(1,2,3,4\)的砖块各\(a_i\)块,两个人轮流操作.
有两种操作,每次只能执行其中一种:

1. 粉碎\(n\)个长度为\(n\)的砖块.

2. 把一个砖块分为两个长度大于\(0\)的砖块.

问先手是否必胜.

HINT

\(a_i\leq10^{10000}\)

Solution

先写个记忆化搜索(\(f[a_1][a_2][a_3][a_4]\)),转移是常数级的.
打个表,发现\(f[a_1][a_2][a_3][a_4]=f[a_1\;mod\;2][a_2\;mod\;3][a_3\;mod\;2][a_4\;mod\;3]\).

xzy:"博弈都不是打表吗?"

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 5
#define M 20
using namespace std;
int f[M][M][M][M],a[N],t,mx;
inline int read(){
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+c-'0';c=getchar();}
	return ret;
}
inline int rd2(){
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)){ret=c-'0';c=getchar();}
	return (ret&1);
}
inline int rd3(){
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)){ret+=c-'0';c=getchar();}
	return ret%3;
}
inline int dfs(int a,int b,int c,int d){
	if(a>mx) mx=a;
	if(b>mx) mx=b;
	if(c>mx) mx=c;
	if(d>mx) mx=d;
	if(!a&&!b&&!c&&!d) return false;
	if(f[a][b][c][d]>-1) return f[a][b][c][d];
	int ret=1;
	if(a>=1) ret&=dfs(a-1,b,c,d);
	if(b>=2) ret&=dfs(a,b-2,c,d);
	if(c>=3) ret&=dfs(a,b,c-3,d);
	if(d>=4) ret&=dfs(a,b,c,d-4);
	if(b) ret&=dfs(a+2,b-1,c,d);
	if(c) ret&=dfs(a+1,b+1,c-1,d);
	if(d) ret&=dfs(a,b+2,c,d-1);
	if(d) ret&=dfs(a+1,b,c+1,d-1);
	return f[a][b][c][d]=(!ret);
}
inline void Aireen(){
	t=read();
	memset(f,-1,sizeof(f));
	while(t--){
		a[1]=rd2();a[2]=rd3();a[3]=rd2();a[4]=rd3();
		printf("%d\n",dfs(a[1],a[2],a[3],a[4]));
	}
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	Aireen();
	fclose(stdin);
	fclose(stdout);
	return 0;
} 

2017-04-05 22:15:15