CF1033G Chip Game

题意

Alice 和 Bob 在玩一个游戏，游戏中有 堆筹码，其中第 堆中有 个筹码。

然后有两个常数 ，每回合 Alice 可以选择一堆取出 个筹码，Bob 可以选择一堆取出 个筹码，直到某回合不能继续操作的一方判负。

假设双方每次都会选择最优策略，对于一对 ，则有四类可能的局面：

  • Alice 必胜。
  • Bob 必胜。
  • 先手必胜。
  • 后手必胜。

在所有 的二元组中，每类局面各出现多少次？

约定

以下假设 ，此时不存在 Bob 必胜。

显然 Alice 必胜的数量跟 Bob 必胜的数量是相等的。

思路

我们先考虑如果 固定了怎么求出输赢情况。

首先就是对于一堆 ，它与 是等价的，我们考虑现在有一个所有 的“最小局面”，那么接下来要证明“最小局面”任意一堆加上一个 ，输赢情况不变。

分两种情况讨论：

  1. 某一方在新加的 中连取了两次：

    那么剩下一个局面，无论哪方胜，他最多有一步的优势，那么我们把这两步中的一步挪到最后，就变成了连取这一方胜，所以这种情况不存在（可能有点奇怪，你可以看作为在后面的局面中另一方有一个不能取这堆的禁手，所以带来了这样的劣势）。

  2. 无人取这新加的 ：

    显然当其他堆取完了，必然要取这堆，所以这种情况不存在。

那么我们就证明了，这一堆必然要被取，并且只要被取，就一定是 Alice 取一次，Bob 取一次。

那么我们将操作重排，一定可以得到双方先取走了新加的这 ，并且先后手不变的一种前两步。

而我们的证明并没有涉及原先是“最小局面”，所以重复这个过程，即可得到非“最小局面”的任意情况。

于是我们所有的 都对 取了模，然后考虑下一步。

接下来会有以下四种点：

  1. 亡点：，这种完全不用管。
  2. A 点：，必然由 Alice 取走。
  3. 半 A 点：，这个点如果 Alice 取了变成 A 点，如果 Bob 取了变成亡点。
  4. 中立点：，任意一方取了变成亡点。

然后讨论一下获胜情况：

  1. 仅存在中立点，且为奇数，先手必胜；
  2. 仅存在中立点，且为偶数，后手必胜；
  3. 存在 A 点，Alice 必胜；
  4. 如果存在一个半 A 点，中立点为奇数，那么 Alice 必胜；
  5. 如果存在一个半 A 点，中立点为偶数，那么先手必胜；
  6. 如果存在多于一个半 A 点，Alice 必胜。

对于 显然，然后 考虑双方第一步都一定是取半 A 点并转化为 。

那么我们可以判定输赢情况，考虑如何计数。

由于我们需要对所有 ，所以我们先枚举 。

接下来，我们对所有点排序，然后枚举 的范围，这样 也确定下来，显然如果存在 那么 Alice 必胜，所以我们快进到 。

那么这样就没有 A 点了，我们需要考虑是否存在半 A 点，即 ，然后用次大值限制一下，把两个半 A 点的情况再划到 Alice 必胜中。

然后对于仅有一个半 A 点以及没有半 A 点的情况，中立点的个数是十分好算的（因为 的可能的范围不跨过任何一个 ）。

这样完成一次计数的时间是 的。

由于有排序，总的时间复杂度 。

CODE

但是这是我在搬题的模拟赛上 4h 写的代码，现在我不知道我当时在写什么。

我找到当时写的题解了，让我搬过来：

然后枚举 的值（设其为 ），这样模意义下的 就是确定的。

然后考虑维护一个序列表示当 为某个值时，决策的情况。

那么对于每个 就会有：

  1. 令 含有左点。

    这种情况记录最大值即可。

  2. 令 增加一个半左点。

    这种情况记录最大值和次大值，次大值之后的视为有左点。

  3. 反转 的中立点情况。

    这种排序以后跟前面两种标记分讨亿下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=200010,FSIZE=1<<13;
using ll=long long;
int n,c,b[N];
ll a[N],leftwin,firstwin,lastwin;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void check(int x){
    bool half=0;
    for(int i=1;i<=n;++i)
        half^=a[i]%(x+x)>=x;
    ++(half?firstwin:lastwin);
}
void get(int x){
    int l=max(1,x-c),r=min(c,(x>>1)-1+(x&1)),maxa=0,maxs0=0,maxs1=0;
    for(int i=1;i<=n;++i){
        b[i]=a[i]%x;
        maxa=max(maxa,min(x-b[i]-1,b[i]));
        if(b[i]>>1>maxs0){
            maxs1=maxs0;
            maxs0=b[i]>>1;
        }else if(b[i]>>1>maxs1) maxs1=b[i]>>1;
        b[i]=min(b[i],r);
    }
    maxa=max(maxa,max(maxs1,l-1));
    maxs0=max(maxa,maxs0);
    leftwin+=maxa-l+1;
    sort(b+1,b+n+1);
    if(b[n]<l){
        lastwin+=(r-l+1)<<1;
        return;
    }
    int i=1;
    for(;b[i]<l&&i<=n;++i);
    for(;b[i]<=maxa&&i<=n;++i);
    for(;b[i]<=maxs0&&i<=n;++i)
        if((n-i+1)&1) firstwin+=(b[i]-max(b[i-1],maxa))<<1;
        else leftwin+=b[i]-max(b[i-1],maxa);
    if(i<=n){
        if((n-i+1)&1) firstwin+=(maxs0-max(b[i-1],maxa))<<1;
        else leftwin+=maxs0-max(b[i-1],maxa);
        ((n-i+1)&1?firstwin:lastwin)+=(b[i]-maxs0)<<1;
    }
    for(++i;i<=n;++i)
        ((n-i+1)&1?firstwin:lastwin)+=(b[i]-b[i-1])<<1;
    lastwin+=(r-b[n])<<1;
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(c);
    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=1;i<=c;++i) check(i);
    for(int i=3;i<c+c;++i) get(i);
    printf("%lld %lld %lld %lld\n",leftwin,leftwin,firstwin,lastwin);
    fclose(stdin);
    fclose(stdout);
    return(0);
}
≡