有一个 \(m\times n\) 大小的网格，每个格子上都堆放了一些 \(1\times 1\times 1\) 的单位立方体，每个格子里堆放的立方体数量都在 \([l,r]\) 内。现在可以对这些网格施加两种操作：
- 指定一个格子，在上面新加两个方块
- 指定两个相邻的格子，在上面各添加一个方块
操作的次数是没有限制的，并且结束的时候方块的高度也没有限制。问这个存在多少种初始状态，可以在有限次操作后做到所有格子上的方块高度都一样。
首先要知道怎么样的初始状态是可以被弄平整的。操作一可以让所有奇偶性相同的格子变成同一高度，操作二可以让两个格子的奇偶性同时变化。显然，只有高度为奇数的格子与高度为偶数的格子的数量均为奇数的时候，这样的初始状态才是没法达到同一高度的。
所以 \(mn\) 是奇数的时候，答案就是 \((r-l+1)^{mn}\)，而 \(mn\) 是偶数的时候答案是：
\[\sum_{i=0}^{mn}\binom{mn}{i}O^{i}E^{mn-i}[i\equiv 0\pmod 2] \]其中 \(O,E\) 表示 \([l,r]\) 内奇数的数量和偶数的数量。
这个式子的形式很容易让人联想到二项式定理，只需要将 \((O+E)^{mn}\) 展开式中指数是偶数的项取出来就行了。这也是一个十分常见的小技巧，将这个式子与 \((O-E)^{mn}\) 加起来就可以抵消掉那些不需要的项。在这个问题中，容易发现 \(|O-E|\in\lbrace 0,1\rbrace\)，甚至连快速幂都不需要用。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll qpow(ll b, ll k) {
b %= mod;
ll ret = 1;
while (k) {
if (k & 1)
ret = ret * b % mod;
b = b * b % mod;
k >>= 1;
}
return ret;
}
ll n, m, l, r;
int main(int argc, char **argv) {
cin >> n >> m >> l >> r;
ll ans = qpow(r - l + 1, n * m);
if (n * m % 2 == 0) {
ans = (ans + (r - l + 1) % 2) * qpow(2, mod - 2) % mod;
}
cout << ans << endl;
return 0;
}