CF1332E Height All the Same 做题记录

最近，Alice 迷上了一款名为 Sirtet 的游戏。

在 Sirtet 中，玩家会得到一个 $n \times m$ 的网格。初始时，格 $(i, j)$ 上码放有 $a_{i, j}$ 个方块。若两个格子有一条公共边，我们称这两个格子时相邻的。玩家可以进行以下两种操作：

• 在两个相邻的格子上各码上一个方块。
• 在一个格子上码上两个方块。

上述中所提到的所有方块都具有相同的高度。

玩家的目标是通过这些操作，使得所有的格子拥有同样的高度（也就是说，每个格子上堆放的方块数相同）。

然而，Alice 发现存在有某些初始局面，使得无论她采用什么策略，都无法达到目标。因此，她希望知道有多少初始局面，满足，

• 对于所有的 $1 \le i \le n$，$1 \le j \le m$，$L \le a_{i, j} \le R$。
• 玩家可以通过执行这些操作，达到目标。

请帮助 Alice 解决这个问题。注意答案可能很大，请输出所求答案对 $998244353$ 取模的值。

观察到奇偶性相同的情况下只要不断应用操作 $2$ 就可以达到目标，所以问题就转化为求能让所有 $a_{i,j}$ 奇偶性相同的方案数。

改变奇偶性的操作只有操作 $1$，它一次可以改变相邻两个位置的奇偶性。不难发现，对于两个位置 $(x1,y1)$ 和 $(x2,y2)$，只要在它们之间的最短路上相邻的每两个位置都操作一次，就可以只改变 $a_{x1,y1}$ 和 $a_{x2,y2}$ 的奇偶性而不对其它的位置造成影响。所以问题就转化为：

有多少个 $n\times m$，元素值域 $[L,R]$ 的网格满足可以通过任意多次改变恰好两个位置奇偶性来让所有元素的奇偶性相同？

不难发现，这个操作并不能改变奇元素个数的奇偶性和偶元素个数的奇偶性，所以一个网格满足条件当且仅当奇元素个数和偶元素个数中有至少一个是偶数。

那么显然 $nm$ 为奇数时网格的所有元素都可以任意取，方案数为 $(R-L+1)^{nm}$。

当 $nm$ 为偶数时，设 $[L,R]$ 内偶数有 $E$ 个，奇数有 $O$ 个，那么方案数为：

$\sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}$

发现这个很像二项式定理，那么考虑：

$(E+O)^{nm}=\sum\limits_{i=0}^{nm}\binom{nm}{i}E^iO^{nm-i}$

把奇数项和偶数项拆开看：

$\sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}+\sum\limits_{i=1}^{\frac{nm}{2}}\binom{nm}{2i-1}E^{2i-1}O^{nm-2i+1}$

前面部分正好是我们想要的，考虑消去后面的部分，观察到：

$(E-O)^{nm}=\sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}-\sum\limits_{i=1}^{\frac{nm}{2}}\binom{nm}{2i-1}E^{2i-1}O^{nm-2i+1}$

中间是减号是因为后面 $O$ 的指数是奇数，系数是 $-1$。

所以

$\begin{aligned} \sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}&=\frac{\left(\sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}+\sum\limits_{i=1}^{\frac{nm}{2}}\binom{nm}{2i-1}E^{2i-1}O^{nm-2i+1}\right)+\left(\sum\limits_{i=0}^{\frac{nm}{2}}\binom{nm}{2i}E^{2i}O^{nm-2i}-\sum\limits_{i=1}^{\frac{nm}{2}}\binom{nm}{2i-1}E^{2i-1}O^{nm-2i+1}\right)}{2}\\ &=\frac{(E+O)^{nm}+(E-O)^{nm}}{2} \end{aligned}$

有个细节就是快速幂要特判底数为 $0$ 的情况。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int p=998244353,inv2=499122177;

int n,m,L,R;

inline int qpow(int x,int y)
{
	if(x==0) return 0;
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=(y&1)?1ll*res*x%p:res;
	return res;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&L,&R);
	if(1ll*n*m&1)
	{
		printf("%d\n",qpow((R-L+1)%p,1ll*n*m%(p-1)));
	}
	else
	{
		int E=(R-L+1)/2+((L&1)==(R&1)),O=R-L+1-E;
		E%=p,O%=p;
		int val=1ll*n*m%(p-1);
		printf("%d\n",1ll*(qpow((E+O)%p,val)+qpow((E-O+p)%p,val))%p*inv2%p);
	}
	return 0;
}