题意

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

分析

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

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

那么 n m n*m nm 为偶数时呢?
可以发现,由上述观察,我们可以发现,满足条件为:有偶数个 0 0 0 格子和偶数个 1 1 1 格子,这样才可能消完 0 0 0 1 1 1。假设 [ L , R ] [L,R] [L,R] x x x 个奇数, y y y 个偶数,那么我们枚举 1 1 1 格子的数量,有:
a n s = <munder> i = 0 , 2 , 4 , . . . 2 k </munder> C n m i x i y n m i ans=\sum\limits_{i=0,2,4,...2k}C_ {nm}^i*x^i*y^{nm-i} ans=i=0,2,4,...2kCnmixiynmi
其实就是二项式定理取偶数项。
要得到 a n s ans ans,只需要 ( ( x + y ) n m + ( x y ) n m ) / 2 ((x+y)^{nm}+(x-y)^{nm})/2 ((x+y)nm+(xy)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;
}