传送门

题目大意

有 \(n\) 个石子堆，每堆有 \(a_i\) 个石子。A 与 B 轮流取，A 每次只能取 \(x\) 个，B 每次只能取 \(y\) 个。

求对于所有 \(x,y \in [1,m]\)，A 必胜、B 必胜、先手必胜和后手必胜的数量。

\(n \le 100,m \le 10^5,a_i \le 10^{18}\)。

思路

A 必胜和 B 必胜本质是相同的。所以我们只需要考虑先手必胜和后手必胜。

我们很容易猜到将数组对 \(x+y\) 取模。

如果取模后的状态先手必胜，那么先手第一步按照取模后的必胜策略进行，之后一直与后手拿同一堆，变为取模后的局面。那么这样原状态先手必胜。

如果取模后的状态后手必胜，后手可以一直拿与先手相同的堆，变为取模后的局面。此时原状态后手必胜。

所以取模后的局面与原局面必胜状态相同。

我们先假设 \(x \le y\)。

我们取模之后会出现四种类型的堆：

\(a_i \in [0,x)\)，没用。
\(a_i \in [x,y)\)，A 拿变为类型 \(1\)，B 不能拿。
\(a_i \in [y,2x)\)，A,B 拿都会变为类型 \(1\)。（\(y \ge 2x\) 则不存在）
\(a_i \in [\max(2x,y),x+y)\)，A 拿变为类型 \(2\)，B 拿变为类型 \(1\)。

然后我们进行大力分类讨论。我们定义 \(t_i\) 表示第 \(i\) 种类型的堆的个数。

\(t_2 \ge 1\)：A 必胜。
\(t_2 = 0\)：
- \(t_4 \ge 2\)：A 肯定可以让一个类型 \(4\) 变为类型 \(2\)，A 必胜。
- \(t_4 = 1\)：
  - \(t_3\) 为奇数：
    - A 先手：A 把类型 \(4\) 变为类型 \(2\)，A 必胜。
    - B 先手：B 只能先抢类型 \(4\)，但是接下来一人拿一堆还是必败。A 必胜。
  - \(t_3\) 为偶数：先手必胜。
- \(t_4 = 0\)：
  - \(t_3\) 为奇数：先手必胜。
  - \(t_3\) 为偶数：后手必胜。

记住我们只关注先手必胜和后手必胜。所以我们整理为如下：

先手必胜：\(t_2=0\)，\(t_4=1\) 且 \(t_3\) 是偶数或 \(t_4=0\) 且 \(t_3\) 是奇数。

后手必胜：\(t_2=0\)，\(t_4=0\) 且 \(t_3\) 是偶数。

转化为数学语言：

先手必胜：\(\forall a_i,a_i \not \in [x,y)\)，\(\sum[a_i \ge \max(2x,y)] \le 1\)，\(\sum[a_i \ge y]\) 为奇数。

后手必胜：\(\forall a_i,a_i \not \in [x,y)\)，\(\sum[a_i \ge \max(2x,y)] = 0\)，\(\sum[a_i \ge y]\) 为偶数。

如果直接枚举就可以达到 \(O(nm^2)\) 的复杂度，但是显然过不去。

因为我们是对 \(x+y\) 取模，所以我们可以直接枚举 \(x+y\)。令 \(s=x+y\)。

然后取模之后对整个数组排序，因为 \(\forall a_i,a_i \not \in [x,y)\) 等价与给 \(a\) 排序之后 \(x,y\) 都在相邻两个数之间。

再枚举 \(x\) 和 \(y\) 出现在 \(a_i\) 和 \(a_{i+1}\) 之间。

我们发现，排序之后其实 \(\sum[a_i \ge y]\) 我们也知道了。接下来就是解决 \(\sum[a_i \ge \max(2x,y)]\)。

对于先手，\(\sum[a_i \ge \max(2x,y)] \le 1\)，等价于 \(\max(2x,y) > a_{n-1}\)。

\(\max\) 很难搞，但是实际上，\(x,y\) 在相邻两个数之间，所以如果 \(y > a_{n-1}\)，\(2x > x > a_{n-1}\)。所以只需要计算 \(2x > a_{n-1}\)。

这样就可以计算出 \(x \in [l,r]\)，其中 \(l = \max(a_i,\lfloor \frac{a_{n-1}}{2} \rfloor) + 1 , r = \min(\frac{s}{2},\min(m,a_{i+1}))\)。\(\frac{s}{2}\) 是因为我们一开始假设 \(x \le y\)。

考虑把 \(x \le y\) 的条件去掉。这个时候其实就是 \(x'=\min(x,y),y'=\max(x,y),x' \in [l,r],y' \in [a_i+1,r],l = \max(a_i,\lfloor \frac{a_{n-1}}{2} \rfloor) , r = \min(a_{i+1},m)\)。

把 \(x'\) 和 \(y'\) 拆开，得到 \(x \ge l,y \ge l,x \le r,y \le r\)。

最终代入 \(y=s-x\) 得到答案为 \(x \in [\max(l,s-r),\min(r,s-l)]\)。

因为一个 \(x\) 对应唯一的 \(y\)，所以 \(\min(r,s-l)-\max(l,s-r)+1\) 就是枚举的 \(x+y\) 对答案的贡献。

后手同理。

最后用总方案 \(m^2\) 减去先手必胜和后手必胜，再除以 \(2\) 即可得到 A 必胜与 B 必胜了。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
const ll N=1e6+10;
using namespace std;

ll n,m;
ll a[N],b[N];
ll ans1,ans2;//ans1是先手必胜，ans2是后手必胜

int main(){
	
	scanf("%lld%lld",&n,&m);
	For(i,1,n)scanf("%lld",&a[i]);
	
	For(s,2,m*2){//枚举x+y
		b[n+1]=s-1;//插入一个最大值
		For(i,1,n)b[i]=a[i]%s;//取模
		sort(b+1,b+n+1);//排序
		For(i,0,n){//x,y在b[i]与b[i+1]间，注意0和n也要枚举
			ll t=(n-i)%2;//大于等于y的个数的奇偶性
			if(t==1){//计算先手必胜
				ll l=max(b[i],b[n-1]/2)+1,r=min(b[i+1],m);
				ans1+=max(0ll,min(r,s-l)-max(l,s-r)+1);
			}else{//计算后手必胜
				ll l=max(b[i],b[n]/2)+1,r=min(b[i+1],m);
				ans2+=max(0ll,min(r,s-l)-max(l,s-r)+1);
			}
		}
	}
	ll ans=(m*m-ans1-ans2)/2;//A必胜与B必胜
	printf("%lld %lld %lld %lld",ans,ans,ans1,ans2);
	
	return 0;
}