题解：P6819 [PA2012] Binary Dodgeball

· · 题解

好玩的题目。

Solution

考虑判定一个局面是先手必胜还是后手必胜。一眼丁真每个棋子都是独立的，所以直接启动 {\rm SG}。

然后发现每个状态的后继都是一个链状的结构，这跟 Nim 游戏是一样的，所以我们知道 {\rm SG}(i)=\lfloor\log_2\frac ni\rfloor。于是一个局面的 {\rm SG} 值 {\rm SG}(1\sim n)=\bigoplus_{1\le i\le n}\lfloor\log_2 \frac ni\rfloor。

枚举每一个值并统计它出现了多少次，推式子：

{\rm SG}(1\sim n)=\bigoplus_{k}\Big(\big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big)\bmod 2\Big)\times k

其中 \big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big) 就是满足 \frac{n}{i}\in [2^k,2^{k+1}) 的 i 的个数。观察一下，发现 \Big(\big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big)\bmod 2\Big) 就是 n 的第 k 位与第 k+1 位是否相同。

接下来考虑拆位，即统计 n 的每一位贡献到 {\rm SG} 值的系数。打表 code：

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
ull f[6];
void init(){
    for(int i=0;i<64;i++)
        for(int j=0;j<6;j++)
            if(i>>j&1)
                f[j]^=3ull<<i;
}
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    init();
    for(int i=0;i<6;i++)
        for(int j=0;j<64;j++)
            cerr<<(f[i]>>j&1)<<" \n"[j==63];
    return 0;
}

打出来的表长这样：

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

不难发现规律：第 0 列的系数均为 0；设 j=\log_2{\rm lowbit}(i)，则 [0,j] 行内第 i 列的贡献系数都是 1，(j,+\infty) 行内第 i 列的贡献系数都是 0。

对它消元，使得每列仅出现一个 1。那么此时的后手必胜要求就是对于每一种 j，所有满足 {\rm lowbit}(i)=j 的数位 i 异或起来是 0。

现在我们有相当好的办法刻画 {\rm SG} 值，直接从高到低确定每一位即可。时间复杂度 O(\log n)。

Code

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
ui n;bool val[64];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;n++;
    ull ans=0,cnt=1ull<<29;
    for(int i=35;i>=1;i--){
        if(!(i&(i-1)))ans|=(ull)val[i]<<i;
        else{
            if(n>cnt)
                n-=cnt,ans|=1ull<<i,val[i&-i]^=1;
            cnt>>=1;
        }
    }
    cout<<(ans+(n>1))<<'\n';
    return 0;
}