51Nod 1714 B君的游戏

Problem

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

双方轮流操作。每次操作，选一个正整数x，将其移除，再添加7个数字 𝑥1,𝑥2...𝑥7 。要求对于 𝑥𝑖 ，满足 0<=𝑥𝑖<𝑥 且 𝑥&𝑥𝑖=𝑥𝑖

注意0不能被选取，所以这个游戏一定会结束，而谁无法操作谁就失败。 B君根据自己的经验，认为先手胜率高一点，所以B君是先手。 B君想知道自己是否必胜。

Solution

SG函数值和数字中1的个数有关，打一个SG函数表。

Code

#include<stdio.h>
#include<set>
#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod=1e9+7;
inline int mo(ll a,int p){
    return a>=p?a%p:a;
}
inline int rd() {
    int x = 0, f = 1;
    char ch;
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}
inline ll gcd(ll x, ll y){
    return y==0?x:gcd(y,x%y);
}
inline ll speed(ll a,ll b,int p){
    ll cur=a,anss=1;
    while(b){
        if(b&1) anss=anss*cur%p;
        cur=cur*cur%p;
        b>>=1;
    }
    return anss%p;
}
const int MAXN=1e5;
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//埃式筛法
    int N=sqrt(MAXN)+0.5,mul;
    memset(ipr,true,sizeof(ipr));
    ipr[1]=false;
    for(int i=2;i<=N;i++){
        if(ipr[i]){
            i==2?mul=1:mul=2;
            for(int j=i*i;j<=MAXN;j+=i*mul){
                ipr[j]=false;
            }
        }
    }
    for(int i=2;i<=MAXN;i++){
        if(ipr[i]){
            pri[++cnt]=i;
        }
    }
}
ll sg[100020];
ll fg[10020];
int gn1(ll x){
    int ret=0;
    while(x){
        ret++;
        x=x&(x-1);
    }
    return ret;
}
void dfs(int mx,int dep,int sum){
    if(dep==0){
        fg[sum]=1;
        return;
    }
    for(int i=0;i<=mx;i++){
        dfs(i,dep-1,sum^sg[i]);
    }
}
void getsg(int n=64){
    for(int i=1;i<=n;i++){
        memset(fg,0,sizeof(fg));
        dfs(i-1,7,0);
        for(int j=0;;j++){
            if(!fg[j]){
                sg[i]=j;
                break;
            }
        }
    }
}

int a[120]={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,23734709};
int main(){
    //io_opt;
    /*getsg();
    cout<<"int a[120]={0,";
    for(int i=1;i<=64;i++){
        cout<<sg[i];
        if(i!=64) cout<<",";
        if(i%10==0) cout<<endl;
    }
    cout<<"};";*/
    int n,tmp,ans=0;
    ll x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        tmp=gn1(x);
        ans^=a[tmp];
    }
    if(ans==0){
        printf("L\n");
    }
    else{
        printf("B\n");
    }
    return 0;
}