hdu3404 Switch lights-----NIM积

Switch lights

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 215    Accepted Submission(s): 115

Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<cstring>#include<cstdio>using namespace std;int sg[20][20];int f(int,int);//声明一下，因为f与g互相嵌套调用int g(int x, int y)//计算2^x与2^y的nim积{ if(sg[x][y] != -1)//查备忘录 { return sg[x][y]; } if(!x)//x==0也就是1与2^y的nim积，等于2^y { return sg[x][y] = 1<<y; } if(!y)//同上 { return sg[x][y] = 1<<x; } int ans=1,k=1,t; int x1=x,y1=y; while(x||y)//再将x和y分为二进制，这里计算那些普通乘积的（即对应二进制位不同的） { t = 1<<k;//从此位得到的最终的数2^k if((x&1||y&1) && !((x&1)&&(y&1)))//该位不同 { ans *= t; } x >>= 1; y >>= 1; k <<= 1;//从此位得到的指数(本身也是2的幂) } k = 1; x = x1; y = y1; while(x||y)//计算那些相同的fermat 2-power 数，与已得出的数的nim积 { t = 1<<k; if((x&1)&&(y&1))//该位相同 { ans = f(ans,t/2*3); } x >>= 1; y >>= 1; k <<= 1;//从此位得到的指数(本身也是2的幂) } return (sg[x1][y1] = ans);}int f(int x, int y)//计算二维的nim积{ if(!x || !y)return 0; if(x == 1)return y; if(y == 1)return x; int ans = 0; for(int i = x,a = 0; i; i>>=1,a++)//完成（将x和y分解后）按分配律计算其积 { if((i&1)==0)continue;//该位（bit）是1才计算，否则跳过 for(int j = y,b = 0; j; j>>=1,b++) { if((j&1)==0)continue; ans ^= g(a,b); } } return ans;}int main(){ int x,y,t; int n,ans; scanf("%d",&t); while(t--) { memset(sg,-1,sizeof(sg)); scanf("%d",&n); ans = 0; while(n--) { scanf("%d%d",&x,&y); ans ^= f(x,y); } puts(ans ? "Have a try, lxhgww." : "Don't waste your time."); } return 0;}