【2018 BSUIR Final C】Partial Sums 题解

题目大意

  给定一个 $n \times m$ 的 01 矩阵 $A_0$。定义一次操作为将这个矩形每个元素求异或前缀和，即 $A_k[i,j]=(\sum_{u=1}^i\sum_{v=1}^j A_{k-1}[u,v]) \bmod 2$。
  求一个最小的正整数 $k$，使得 $A_0=A_k$。

  $n\times m \leq 10^6$

$$\\$$ $$\\$$ $$\\$$

题解

  首先，可以发现答案一定是 $2$ 的幂。
  可以这么说明这个结论，设 $k_{i,j}$ 表示左上角为 $(1,1)$ 右下角为 $(i,j)$ 的子矩形的答案，那么 $k_{i,j}$ 至少为 $lcm(k_{i-1,j},k_{i,j-1})$，如果这 $lcm$ 轮过后 $(i,j)$ 的元素没变，那么 $k_{i,j}$ 就等于这个，否则还要再来 $lcm$ 轮把它变回来，即 $k_{i,j}=lcm \cdot 2$。而又因为 $k_{1,1}=1$，因此可以归纳证明任意 $k_{i,j}$ 一定是 $2$ 的幂。

  然后想一个问题，如果经过 $k$ 轮操作，那么一个格子 $(x,y)$ 对其右下的一个格子 $(x+\Delta x,y+\Delta y)$ 的贡献是多少？
  这等价于一个棋子从 $(x,y)$ 开始，每次跳到其右下方的一个位置（包括自己本身），跳 $k$ 步跳到 $(x+\Delta x,y+\Delta y)$，的方案数是多少。
  这显然是 $\binom{\Delta x+k-1}{k-1} \cdot \binom{\Delta y+k-1}{k-1}$。
  而根据 Lucas 定理，当 $k$ 为 $2$ 的幂时，只有当 $\Delta x$ 和 $\Delta y$ 都是 $k$ 的倍数的时候，这个式子才 $\bmod~2=1$。

  于是我们就可以 $k=1,2,4,8,\cdots$ 这样枚举答案，每次枚举中，每个位置只考虑 $\Delta x$ 和 $\Delta y$ 是 $k$ 倍数的位置的贡献，可以 $O(nm)$ 得出最终矩阵并判断。（看代码）
  同时这样也说明答案不会很大，最多判断 $\log nm$ 次。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=1e6+5;

int n,m;
bool a[maxn];

inline int id(int i,int j) {return (i-1)*m+j;}

void ReadBit(bool &data)
{
	char ch=getchar();
	while (ch!='0' && ch!='1') ch=getchar();
	data=(ch=='1');
}

bool b[maxn];
bool check(int k)
{
	fo(i,1,n)
		fo(j,1,m)
		{
			b[id(i,j)]=a[id(i,j)];
			if (i>k) b[id(i,j)]^=b[id(i-k,j)];
			if (j>k) b[id(i,j)]^=b[id(i,j-k)];
			if (i>k && j>k) b[id(i,j)]^=b[id(i-k,j-k)];
			if (b[id(i,j)]!=a[id(i,j)]) return 0;
		}
	return 1;
}

int main()
{
	scanf("%d %d",&n,&m);
	fo(i,1,n)
		fo(j,1,m) ReadBit(a[id(i,j)]);
	
	int k=1;
	while (!check(k)) k<<=1;
	
	printf("%d\n",k);
}