CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
#include <iostream>
using namespace std;

__int64 a[
30];
int sg[20][20];
void init()
{
    
int i, j, m, ii, jj;
    
bool fals[200];
    a[
0= 2;
    
for (i = 1; i <= 5; i++)
    {
        m 
= 1;
        
for (j = 1; j <= i; j++)
            m 
*= 2;
        a[i] 
= 1;
        
for (j = 1; j <= m; j++)
            a[i] 
*= 2;
    }
    sg[
1][1= 1;
    
for (i = 1; i <= 15; i++)
    {
        
for (j = 1; j <= 15; j++)
        {
            memset(fals, 
falsesizeof(fals));
            
for (ii = 1; ii <= i; ii++)
                
for (jj = 1; jj <= j; jj++)
                {
                    
if (ii == i && jj == j)break;
                    m 
= sg[ii][jj];
                    
if (ii < i && jj < j)
                        m 
= m ^sg[ii][j]^sg[i][jj];
                    fals[m] 
= true;
                }
            ii 
= 1;
            
while (fals[ii])ii++;
            sg[i][j] 
= ii;
        }
    }
}
int nim_multi_pow(int x, int y)
{
    
if (x < 16)
        
return sg[x][y];
    
if (x== 0 || y == 0)return 0;
    
int i, m, p, s, t, d1, d2;
    i 
= 0;
    
while (x >= a[i])i++;
    m 
= a[i-1];
    p 
= x/m;
    s 
= y/m;
    t 
= y%m;
    d1 
= nim_multi_pow(p, s);
    d2 
= nim_multi_pow(p, t);
    
return (m*(d1^d2))^nim_multi_pow(m/2,d1);
}

int nim_multi(int x, int y)
{
    
if (x < y) return nim_multi(y, x);
    
if (x < 16return sg[x][y];
    
if (y == 0)return 0;
    
int i, p, m, q, s, t, c1, c2, c3;
    i 
= 0;
    
while (x >= a[i])i++;
    m 
= a[i-1];
    p 
= x/m;
    q 
= x%m;
    s 
= y/m;
    t 
= y%m;
    c1 
= nim_multi(p, s);
    c2 
= nim_multi(p,t)^nim_multi(q, s);
    c3 
= nim_multi(q, t);
    
return ((c1^c2)*m)^c3^nim_multi_pow(m/2, c1);
}

int main()
{
    init();
    
int t, n, i, x, y, z;
    
int ok;
    cin 
>> t;
    
while (t--)
    {
        cin 
>> n;
        ok 
= 0;
        
for (i = 0; i < n; i++)
        {
            scanf(
"%d%d"&x, &y);
            ok 
^= nim_multi(x, y);
        }
        
if (ok)printf("Have a try, lxhgww.\n");
        
else
            printf(
"Don't waste your time.\n");
    }
    
return 0;
}
posted on 2011-05-13 16:12 CodeStream 阅读(371) 评论(0)  编辑 收藏 引用 所属分类: acm_博弈

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理