CF1332E Height All the Same（思维）

题意

有一个 $n\ast m$n∗m 的矩阵，每次可以往一个格子 $+2$+2，或在任意相邻的两个格子 $+1$+1，可以操作无限次。给定一个限制 $[L,R]$[L,R]，问有多少种初始情况满足 $a_{i,j}\in [L,R]$ai,j​∈[L,R]，使得经过若干次操作后所有格子高度相等。

分析

日常感叹我太弱了。。。
首先，由于有 $+2$+2 操作，所以对于任意一个初始矩阵，都可以由一个 $01$01 矩阵不断 $+2$+2 转化而来。所以，我们其实只关心每个位置的奇偶性。
然后对于 $+1$+1 操作，相当于改变相邻两个格子的奇偶性，即是 $0$0 变成 $1$1， $1$1 变成 $0$0。
然后接下来有个重要的观察！

$n\ast m$n∗m 为奇数时，所有初始情况都可行！
为什么呢？当 $n\ast m$n∗m 为奇数时，一定有偶数个格子为 $0$0 或 $1$1。下面考虑偶数个格子为 $1$1 的情况（另一种情况与此等价）。翻转操作我们可以看成在走路。如果相邻位置是 $01$01，相当于交换 $0,1$0,1 的位置；如果相邻位置是 $11$11，那么它们将相消。所以，两个 $1$1 一定是可以相消的，即是从一个 $1$1 走到另一个 $1$1。于是，偶数个 $1$1 格子一定可以化为 $0$0。
所以 $ans=(R-L+1{)}^{nm}$ans=(R−L+1)nm

那么 $n\ast m$n∗m 为偶数时呢？
可以发现，由上述观察，我们可以发现，满足条件为：有偶数个 $0$0 格子和偶数个 $1$1 格子，这样才可能消完 $0$0 或 $1$1。假设 $[L,R]$[L,R] 有 $x$x 个奇数， $y$y 个偶数，那么我们枚举 $1$1 格子的数量，有：
$ans=\sum _{i=0,2,4,...2k}{C}_{nm}^i\ast x^i\ast y^{nm-i}$ans=i=0,2,4,...2k∑​Cnmi​∗xi∗ynm−i
其实就是二项式定理取偶数项。
要得到 $ans$ans，只需要 $\left(\right(x+y{)}^{nm}+(x-y{)}^{nm})/2$((x+y)nm+(x−y)nm)/2 就好了。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int mod = 998244353;
LL z = 1;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
int main(){
	int i, j, n, m, l, r, k, t, inv2;
	inv2 = ksm(2, mod - 2, mod);
	n = read(); m = read(); l = read(); r = read();
	k = (r - l + 1) / 2;
	if(l % 2 && r % 2) k++;
	t = (r - l + 1) - k;//k 为奇数的个数，t 为偶数的个数 
	if(n % 2 && m % 2){
		printf("%d", ksm(ksm(r - l + 1, n, mod), m, mod));
	}
	else{
		i = ksm(ksm(k + t, n, mod), m, mod);
		j = ksm(ksm(k - t, n, mod), m, mod);
		i = z * (i + j) * inv2 % mod;
		i = (i + mod) % mod;
		printf("%d", i);
	}
	return 0;
}