题解：P7977 「Stoi2033」世界未末日

· · 题解

题意简述

有 n 堆石子。一次操作可以同时选择一至 k 堆，并从每堆中移走一个合法数量 c。合法条件是存在实数 a,b，满足 ab=s、a+b=c，且 1\le c\le s。

判断先手是否必胜。

解题思路

先分析一堆石子的合法后继。

把 a,b 看成一元二次方程的两个实根：

x^2-cx+s=0

存在实根当且仅当判别式非负：

c^2-4s\ge0

因为 c 是整数，所以最少移走 \lceil2\sqrt{s}\rceil 个石子。设操作后剩下 y 个，则一堆大小为 s 的石子可以变成所有满足下式的整数：

0\le y\le h(s)

其中：

h(s)=\left\lfloor s-2\sqrt{s}\right\rfloor

当 h(s)<0 时没有合法操作。

记单堆游戏的 SG 函数为 f(s)。函数 s-2\sqrt{s} 在 s\ge1 时单调不降，并且相邻整数处的增量小于 1，所以：

h(s+1)-h(s)\in\{0,1\}

从 f(0)=f(1)=f(2)=f(3)=0 开始归纳。假设 f(0),f(1),\dots,f(s-1) 单调不降，且相邻值至多增加 1。因为一堆 s 可以到达整个整数区间 [0,h(s)]，其中的 SG 值恰好连续覆盖 0 到 f(h(s))。因此：

f(s)=f(h(s))+1

而 h 每次只会保持或增加 1，所以上式也保证 f(s) 每次只会保持或增加 1。归纳条件始终成立。

不能逐个计算到 S。设 d_i 是满足 f(s)=i 的最小 s，其中 d_0=0。下一个 SG 值首次出现，当且仅当 h(s)\ge d_i。由于 d_i 是整数：

\begin{aligned} s-2\sqrt{s} & \ge d_i \\ (\sqrt{s}-1)^2 & \ge d_i+1 \\ s & \ge\left(1+\sqrt{d_i+1}\right)^2 \end{aligned}

因此最小整数阈值满足：

d_{i+1}=d_i+2+\left\lceil\sqrt{4(d_i+1)}\right\rceil

代码用 sqrtl 得到近似平方根，再用整数乘法向两侧校正，保证上取整结果准确。阈值只有 O(\sqrt S) 个。对每个 s 在阈值数组中二分，便能求出 f(s)。

由于大小为 s 的一堆可以到达的 SG 值恰好为 0,1,\dots,f(s)-1，原游戏等价于以下游戏：有若干大小为 f(s_i) 的 Nim 堆，每次把一至 k 堆分别变小。

对每个二进制位 j，统计该位为 1 的堆数，并记其对 k+1 的余数为 C_j。结论是：

\forall j,C_j=0

当且仅当当前局面为必败态。

先证明从这种局面出发的任意操作都会离开它。取本次所有变化中的最高二进制位 j。在这一位发生变化的每个数都必须从 1 变为 0，数量介于 1 和 k 之间。因此 C_j 会减去一个不被 k+1 整除的数，操作后不再为 0。

再证明任意其他局面都能一步进入上述局面。按二进制位从高到低构造一次操作。已经在更高位变小的堆称为已选堆，它们的低位可以任意设置。设当前已有 m 个已选堆，未选堆在当前位共有 u 个 1。

令 q 是区间 [0,k] 中满足下式的唯一整数：

q\equiv-u\pmod{k+1}

若 q\le m，就在已选堆中设置恰好 q 个 1，当前位的总数便能被 k+1 整除。

若 q>m，令 t=k+1-q。由 u\equiv t\pmod{k+1} 且 t>0 可知，未选堆中至少有 t 个当前位为 1 的堆。选择其中 t 个，并把所有已选堆的当前位设为 0。新选择的堆在这一位从 1 变为 0，所以确实变小。同时：

m+t=m+k+1-q\le k

故最终选择的堆数始终不超过 k。逐位处理后，所有 C_j 都变为 0。每个选中 Nim 堆都严格变小，而对应石子堆可以到达任意更小的 SG 值，所以这次操作在原游戏中合法。

代码在读入每一堆时直接把各位计数对 k+1 取模。最后只要存在一个非零计数，先手就必胜。

总时间复杂度为 O(\sqrt S+n\log S)，空间复杂度为 O(\sqrt S)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const int K=20;
ll d[N];
ll ceil_sqrt(ll x)
{
    ll r=sqrtl(x);
    while(r*r<x)r++;
    while(r&&(r-1)*(r-1)>=x)r--;
    return r;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    ll mx;
    cin>>n>>k>>mx;
    int cnt=0;
    while(d[cnt]<=mx)
    {
        d[cnt+1]=d[cnt]+ceil_sqrt(4*(d[cnt]+1))+2;
        cnt++;
    }
    int base=k+1;
    int bit[K]={};
    for(int i=1;i<=n;i++)
    {
        ll s;
        cin>>s;
        int val=upper_bound(d,d+cnt+1,s)-d-1;
        for(int j=0;val;j++,val>>=1)
        {
            if(!(val&1))continue;
            bit[j]++;
            if(bit[j]==base)bit[j]=0;
        }
    }
    for(int i=0;i<K;i++)
    {
        if(!bit[i])continue;
        cout<<"YES"<<'\n';
        return 0;
    }
    cout<<"NO"<<'\n';
    return 0;
}