题解 CF1033G 【Chip Game】

· · 题解

考虑给定 a,b 怎么做.

非常不显然的是,对于所有 v'_i\equiv v_i\mod (a+b) 构成的局面 S',它与所有 v_i 构成的局面 S 本质上是相同的.

证明

我们需要证明的是,对于 S' 中的 winner,他仍可以使自己成为 S 中的 winner

不妨设 S' 中的 winner 为 A ,loser 为 B ,在 S' 中使用的策略为 G'

若 A 为后手,在每次先手 B 操作之后,存在两种情况

  1. 若可以在 B 取的 pile 上取走 a 个chip,那就取走 a 个chip
  2. 否则,在 G' 中应该取走 a 个 chip 的 pile 上取走 a 个 chip

若 A 为先手,那么先在在 G' 中应该取走 a 个 chip 的 pile 上取走 a 个 chip,然后转化为 A 为后手的情况.

接下来考虑 A 通过这种策略 G 是否还是 winner

明确一个事实,即对于两个策略 S,T,对于所有 pile,如果 A 取走的 chip数在这两个策略中均相同,那么这两个策略本质上是相同的.也就是说,取的顺序是无关紧要的.

那么,将 G 中所有一起选的 BA 对(即上面提到的情况1)拉到最前面,可以发现胜负并没有变化,且一定是合法的.

那么,操作完这些一起选的 BA 对之后,局面 S 变为局面 S',且经过了偶数步,先后手并没有交换,所以对于 S' 中的 winner,他仍可以使自己成为 S 中的 winner.

如何计数

值得注意的是,A win 的情况和 B win 的情况是对称的,而且指的是无论他是否先手.这样用总方案数(m^2)减去先/后手必胜的情况再 \div2 即可.

枚举 X=a+b ,将 v 排序,然后对 a 的值分类讨论.

显然,选的值越小越优

钦点先手必败,并且钦点先手选较小的值,设为 a,后手选较大的值,设为 b

如果存在 v_i 满足 a\leq v_i<b,那么先手显然可以win.

如果存在 v_i 满足 2a\leq v_i,那么先手显然也可以win.

那么需要满足的条件就是 \geq a 的 v_i 数量为偶数,且不存在以上两种情况.

对于后手,同理.

代码

#include<bits/stdc++.h>
using namespace std;
#define Ri register
template<typename T>inline T read(Ri T&t)
{Ri T f=1;Ri char ch=getchar();t=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')t=t*10+ch-'0',ch=getchar();t*=f;return t;}
template<typename T,typename...Args>
inline void read(T&t,Args&...args)
{read(t);read(args...);}
const long long p=998244353;
inline long long power(Ri long long x,Ri long long k=p-2)
{Ri long long re=1;for(;k;k>>=1,x=x*x%p)if(k&1)re=re*x%p;return re;}
int n,m;
long long ansA,ansB,ansF,ansL;
long long a[205];
int b[205];
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int S=2;S<=m*2;S++)
    {
        for(int i=1;i<=n;i++)
            b[i+1]=a[i]%S;
        b[1]=0;b[n+2]=S-1;
        sort(b+1,b+n+3);
        for(int i=n+2,id=0;i>1;i--,id^=1)//id=0:先手必败 
        {
            int l=b[i-1]+1,r=min(b[i],m);
            if(id==0)l=max(l,b[n+1]/2+1);
            else l=max(l,b[n]/2+1);
            int L=max(l,S-r),R=min(r,S-l);
            if(L<=R)
                if(id==0)ansL+=R-L+1;
                else ansF+=R-L+1;
        }
    }
    ansA=ansB=(1ll*m*m-ansF-ansL)/2;
    printf("%lld %lld %lld %lld\n",ansA,ansB,ansF,ansL);
    return 0;
}