51Nod 1714 B君的游戏 - dblank

# 51Nod 1714 B君的游戏

1714 B君的游戏

B君和L君要玩一个游戏。刚开始有n个正整数 ai 。

B君根据自己的经验，认为先手胜率高一点，所以B君是先手。
B君想知道自己是否必胜。
Input

Output

Input示例
4
1
2
3
4
Output示例
B

# include<bits/stdc++.h>

typedef unsigned long long ll;
using namespace std;
const int N = 6400000 + 10, Mod = 1000000007;
int sg[100], maxs;
bool vis[N];
void dfs(int up, int m, int ans, int last)
{

if(m == 0)
{
vis[ans] = true;
return ;
}
for(int i = last; i<up; i++)
{
dfs(up, m-1, ans ^ sg[i], i);
}

}
int main()
{

//freopen("D:\\out.txt", "W", stdout);
int n;
int cnt[100];
for(int i = 0; i<=63; i++)
{
memset(vis, 0, sizeof(vis));
dfs(i, 7, 0, 0);
for(int j = 0; j<N; j++)
{
if(vis[j] == false){
sg[i] = j;
break;
}
}
printf("%d,", sg[i]);
}
return 0;

}

AC代码：

# include<bits/stdc++.h>

typedef unsigned long long ll;
using namespace std;
const int N = 1000000 + 10, Mod = 1000000007;
int sg[100], maxs;
ll a[N];

int main()
{
int sg[]={0,1,2,4,8,16,32,64,128,255,256,512,1024,2048,3855,4096,8192,13107,16384,21845,
27306,32768,38506,65536,71576,92115,101470,131072,
138406,172589,240014,262144,272069
,380556,524288,536169,679601,847140,1048576,1072054,1258879,1397519,2005450,2097152,2121415,2496892,2738813,3993667,4194304,4241896,4617503,5821704,7559873,8388608,8439273,8861366,11119275,11973252,13280789,16777216,16844349,17102035,19984054,21979742};

int n;
scanf("%d", &n);
ll ans = 0;
for(int i = 0; i<n; i++){
scanf("%llu", &a[i]);
int num = 0;
for(int j = 0; j<64; j++)
{
if(a[i]  & (1LL<<j))
num++;
}
ans ^= sg[num];
}
if(ans == 0)
printf("L\n");
else printf("B\n");
return 0;

}