题意:一个三维平面里全是灯。每次选出一个正方体,改变八个角灯的状态,而且右下角的灯初始必须是开的。
思路:类似于三维翻硬币游戏。要用到三维Nim积。
学习Nim积的论文:http://www.doc88.com/p-5098170314707.html
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; #define clr(a,b) memset(a,b,sizeof(a)) typedef long long ll; const int maxn=10000+4; const int minn=100+5; int n,sg[2][2]={0,0,0,1}; int Nim_Multi_Power(int x,int y) { if(x<2) return sg[x][y]; int a=0; for(;;a++) if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1)))) break; int m=1<<(1<<a); int p=x/m,s=y/m,t=y%m; int d1=Nim_Multi_Power(p,s); int d2=Nim_Multi_Power(p,t); return (m*(d1^d2))^Nim_Multi_Power(m/2,d1); } int Nim_Multi(int x,int y) { if(x<y) return Nim_Multi(y,x); if(x<2) return sg[x][y]; int a=0; for(;;a++) if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1)))) break; int m=1<<(1<<a); int p=x/m,q=x%m,s=y/m,t=y%m; int c1=Nim_Multi(p,s); int c2=Nim_Multi(p,t)^Nim_Multi(q,s); int c3=Nim_Multi(q,t); return (m*(c1^c2))^c3^Nim_Multi_Power(m/2,c1); } int Nim_Multip(int x, int y, int z){ return Nim_Multi(Nim_Multi(x, y), z); } int main() { int t; while(~scanf("%d",&n)){ int ans=0,x,y,z; for(int i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); ans^=Nim_Multip(x,y,z); } if(ans){printf("No\n");} else {printf("Yes\n");} } return 0; }