题意

给你一个长度为\(n\)的序列和一个数\(m\)。

小A和小B分别在\([1,m]\)选出一个数\(a\)和\(b\)，然后开始游戏。

轮到小A时，他选择一个元素减\(a\)；小B则选择一个元素减\(b\)。

不能将元素变成负数。

问对于所有\(m \times m\)对\((a,b)\)，分别有多少对是小A/B必胜，先/后手必胜。

$ n \leq 100，m \leq 100000 $，序列元素 $ \leq 10^{18} $

思路

首先易知，原序列与原序列\(mod \space a+b\)后得到的结果是一样的，且A必胜与B必胜的情况种类是一样的,所以不妨假设\(a \leq b\)

先取模，然后对后来的序列进行讨论

判断条件1	\(d\)个数\(\geq 2a\)	\(c\)个数\(\geq b\)	判断条件4	情况
$ \exists i$ 使\(a \leq x_i <b\)				A
	\(d \geq2\)			A
		\(c=0\)		后
		\(c \text{ mod } 2=1\)		先
			\(d=1\)	A
			\(d=0\)	后

一个大的分类讨论

枚举\(a+b\)，每次\(O(n \space log n)\)计数，总复杂度\(O(2nm \space log n)\)

#include <bits/stdc++.h>

using std::sort;

using std::min;

using std::max;

int n,m,b[105];

long long a[105],cnt1,cnt2;

int main(){

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

    for (int i=2;i<=2*m;i++){

        for (int j=1;j<=n;j++) b[j]=a[j]%i;

        sort(b+1,b+n+1);

        b[n+1]=m;

        if (~i&1){

            int t1=0;

            for (int j=1;j<=n;j++) if (b[j]>=i/2) t1=t1^1;

            if (t1) cnt2++;

        }

        for (int j=1;j<=n+1;j++){

            int l=max(b[j-1]+1,i/2+1),r=min(min(i-1,m),b[j]);

            if (r<l) continue;

            int al=max(b[j-1],b[n-1]/2),bl=max(l,i-al);

            if (bl<=r) cnt1+=r-bl+1,r=bl-1;

            if (r<l) continue;

            if ((n-j+1)&1) cnt2+=(r-l+1)*2;

            else{

                al=b[n-1]/2+1;int ar=b[n]/2;

                bl=max(l,i-ar);int br=min(r,i-al);

                if (br>=bl) cnt1+=br-bl+1;

            }

        }

    }

    printf("%lld %lld %lld %lld",cnt1,cnt1,cnt2,1ll*m*m-cnt1-cnt1-cnt2);

}

后记

ZJOI2019 kcz讲解了此题，但是写起来还是有点晕，ZJOI开心地爆了