题意
对于一个(n*m)的矩阵，有两种操作
- 一个格子加二
- 一个格子和另一个相邻的格子同时加一
通过这两种操作最终使得所有矩阵元素相等
对于矩阵元素来说，有(Lleq a_{i,j}leq R(1leq ileq n,1leq jleq m))
问有多少种方案数，答案(mod 998244353)
分析
由于最终相等的值与答案无关，所以我们不妨所有元素减去(L)，即所有元素的值在([0,R-L])区间内
而所有元素通过操作可以相差最多为(1)（仅仅分奇偶）
这种操作可以不断进行，所以我们只需看数字的奇偶性
为描述，我们不妨将所有元素视为(0,1)
对于(1)来说，其周围一定没有(1)，否则可以填上使两元素变为(0)，那么如果该(1)和旁边的(0)同时加(1)，我们可以发现(0)和(1)互换位置了
这种操作的意义在于，对于任意的一个(1)，我们可以通过操作使其变到其他任意的位置
那么如果矩阵中有奇数个(1)，我们可以将其变为(1)个(1)，而偶数个(1)，我们一定可以将两个(1)进行配对，从而消去
我们思考(n*m)的奇偶性
- 若(n*m)为奇数，若有偶数个(1)，则满足条件，若有奇数个(1)，我们将其变为(1)个(1)，并将其移动到边角上，通过蛇形配对，我们可以将除该元素的其他元素同时加上(1)，所有元素相等，因此所有取值皆满足答案就是((R-L+1)^{n*m})(每个数有(R-L+1)中取法)
- 若(n*m)为偶数，若有偶数个(1)，则满足条件，若有奇数个(1)，我们可以发现元素和为奇数，而(n*m)为偶数，元素和无论怎么增加（每次加二），一定是奇数，无法整除(n*m)一定不满足，因此答案为偶数个(1)的取值方式
接下来分析(n*m)为偶数时，有多少种偶数个(1)的取值方式：
如果(R-L+1)为奇数，则可以取(frac {R-L+2} {2})种奇数，否则为(frac {R-L+1} {2})种奇数，设为(j)，设(R-L+1)为(t)
答案为(C^0_{n*m}*j^0*(t-j)^{n*m}+C^2_{n*m}*j^2*(t-j)^{n*m-2}+cdots+C^{n*m}_{n*m}*j^{n*m}*(t-j)^{0})，意思为挑偶数（(2*k)）个奇数（(C^{2*k}_{n*m})），每个奇数有(j)中取值，其余偶数有(t-j)种取值
发现这个式子是二项展开式的偶数项，那么可以推导下（半小时无从下手，我对不起高中数学老师）
第二个式子偶数项是加号，奇数项是减号（从(0)开始计数）
两式相加除以二即为偶数项和，即
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int qp(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
signed main() {
start;
int n, m, L, R;
cin >> n >> m >> L >> R;
int t = R - L + 1;
if ((n * m) & 1) {
cout << qp(t, n * m) % mod;
} else {
int j;
if (t & 1)
j = (t + 1) / 2;
else
j = t / 2;
int ans = ((qp(t, m * n) + qp((2 * j - t), m * n)) % mod + mod) % mod * qp(2, mod - 2) % mod;
cout << ans;
}
return 0;
}