【2022 NOIP 模拟赛 34】矩阵博弈 做题记录

小 C 将 $r\times c$ 堆石子摆成一个 $r\times c$ 的矩形 $a$，每一轮玩家可以从 $r$ 行中选择任意几行（至少一行），然后从选择的行中各选择非空的一堆石子，拿走其中的一个石子，形式化的说，你可以选择若干正整数 $1\leq i_1<i_2<\dots<i_k\leq r$，然后选择 正整数 $1\leq j_1,j_2,\dots,j_k\leq c$，然后将所有 $a_{i_l,j_l}\ \ (1\leq l\leq k)$ 减一，且保证操作完后非负 。不能操作的人输。你先手操作。

现在有 $n\times m$ 堆石子摆成了一个 $n\times m$ 的矩形，第 $i$ 行第 $j$ 列有 $a_{i,j}$ 个石子，小 C 会在这个矩形中随机选择一个子矩形进行游戏。

你想要知道你获胜的概率乘以 $\frac{nm(n+1)(m+1)}{4}$ 的值，可以证明这一定是个整数。

$1\le n,m\le 3000$，$0\le a_{i,j}\le 10^9$。

首先不难发现答案就是先手必胜子矩形个数，并且不难证明一个子矩形是先手必胜当且仅当这个子矩形有至少一行的和为奇数。

考虑容斥，问题转化为求有多少个子矩形所有行的和都是偶数。

设 $sum_{i,j}=\sum\limits_{k=1}^ja_i\operatorname{mod}2$，那么若固定了子矩形的上边界 $lb$ 和下边界 $rb$，那么子矩形 $(lb,x,rb,y)$ 合法当且仅当 $sum_{lb,x-1}=sum_{lb,y},sum_{lb+1,x-1}=sum_{lb,y},\dots,sum_{rb,x-1}=sum_{rb,y}$。

那么维护若干个等价类，每个等价类的贡献即为 $\frac{siz(siz-1)}{2}$。

考虑如何快速维护等价类，显然下边界往上推一位相当于去掉最后一位的影响，也就是在 trie 上合并两棵子树，那么维护一下即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout);

const int MS=3005;

int n,m,a[MS][MS];
int cnt=1,siz[MS*MS],son[MS*MS][2];
long long pre,ans;

void dfs(int u)
{
	if(son[u][0]!=0) dfs(son[u][0]);
	if(son[u][1]!=0) dfs(son[u][1]);
	siz[u]+=siz[son[u][0]]+siz[son[u][1]];
	pre+=1ll*siz[u]*(siz[u]-1)/2;
}

int meg(int x,int y)
{
	if(x==0||y==0) return x+y;
	son[x][0]=meg(son[x][0],son[y][0]);
	son[x][1]=meg(son[x][1],son[y][1]);
	pre+=1ll*siz[x]*siz[y];
	siz[x]+=siz[y];
	return x;
}

int main()
{
	fio("matrix");
	int T;
	scanf("%d",&T);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			a[i][j]&=1,a[i][j]^=a[i][j-1];
		}
	}
	for(int i=0;i<=m;i++)
	{
		int u=1;
		for(int j=n;j>=1;j--)
		{
			if(son[u][a[j][i]]==0) son[u][a[j][i]]=++cnt;
			u=son[u][a[j][i]];
		}
		siz[u]++;
	}
	dfs(1);
	int rt=1;
	for(int i=n;i>=1;i--)
	{
		pre-=1ll*m*(m+1)/2;
		ans+=pre;
		rt=meg(son[rt][0],son[rt][1]);
	}
	printf("%lld\n",1ll*n*(n+1)/2*m*(m+1)/2-ans);
	return 0;
}