http://poj.org/problem?id=3533

變成三維的nim積。。前面hdu那個(gè)算二維nim積的題的函數(shù)都不用改，多nim積一次就過(guò)了。。。longlong似乎不必要但是還是加上了

代碼

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<map> 7 #include<ctime> 8 using namespace std; 9 long long n; 10 long long sg[21][21]={}; 11 long long f(long long,long long); 12 long long g(long long x,long long y){ 13 if(sg[x][y]!=-1)return sg[x][y]; 14 if(!x)return sg[x][y]=1<<y; 15 if(!y)return sg[x][y]=1<<x; 16 long long ans=1,k=1,t; 17 long long x1=x,y1=y; 18 while(x||y){ 19 t=1<<k; 20 if((x^y)&1){ 21 ans*=t; 22 } 23 x>>=1;y>>=1;k<<=1; 24 } 25 k=1;x=x1;y=y1; 26 while(x||y){ 27 t=1<<k; 28 if((x&y)&1){ 29 ans=f(ans,t/2*3); 30 } 31 x>>=1;y>>=1;k<<=1; 32 }return sg[x1][y1]=ans; 33 } 34 long long f(long long x,long long y){ 35 if(!x||!y)return 0; 36 if(x==1)return y; 37 if(y==1)return x; 38 long long ans=0; 39 for(long long i=x,a=0;i;i>>=1,a++){ 40 if(!(i&1))continue; 41 for(long long j=y,b=0;j;j>>=1,b++){ 42 if(!(j&1))continue; 43 ans^=g(a,b); 44 } 45 }return ans; 46 } 47 int main(){ 48 memset(sg,-1,sizeof(sg)); 49 while(~scanf("%lld",&n)){ 50 long long ans=0,x,y,z; 51 for(long long i=1;i<=n;i++){ 52 scanf("%lld%lld%lld",&x,&y,&z); 53 ans^=f(z,f(x,y)); 54 } 55 if(ans)printf("No\n"); 56 else printf("Yes\n"); 57 } 58 return 0; 59 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/137shoebills/p/8340884.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3553 Light Switching Game 博弈论 nim积 sg函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。