数学、二项式反演

令堆了奇数个块的位置的数量为 $X$，堆了偶数个块的位置的数量为 $Y$。

观察一阵，发现操作要么不改变 $X,Y$ 的值，要么使得 $X \leftarrow X-2$，$Y \leftarrow Y+2$ 或 $X \leftarrow X+2$，$Y \leftarrow Y-2$。所以给定初始形态能将所有方块叠到同一高度当且仅当初始形态中 $X \bmod 2 = 0$ 或 $Y \bmod 2 = 0$。

首先计算合法奇数取值数量记为 $odd$，合法偶数取值数量记为 $even$。

分类讨论，若 $nm$ 为奇数则答案如下。

$$\sum\limits_{i=0}^{nm} [i \bmod 2 = 0] C_{nm}^{i} odd^{i} even^{nm-i} + \sum\limits_{i=0}^{nm} [i \bmod 2 = 0] C_{nm}^{i} odd^{nm-i} even^{i}$$

很显然如果没有 $[i \bmod 2 = 0]$ 这个条件就能二项式反演，于是再操作一波，只考虑加号前面的式子，加号后面的式子按照相同方式计算。

$$\sum\limits_{i=0}^{nm} [i \bmod 2 = 0] C_{nm}^{i} odd^{i} even^{nm-i} =\dfrac{(odd + even)^{nm} - (odd - even)^{nm}}{2}$$

得到答案。

$$\dfrac{(odd + even)^{nm} - (odd - even)^{nm}}{2} + \dfrac{(odd + even)^{nm} - (even - odd)^{nm}}{2}$$

$$(odd + even)^{nm} - \dfrac{(odd - even)^{nm} + (even - odd)^{nm}}{2}$$

若 $nm$ 为偶数则答案如下。

$$\sum\limits_{i=0}^{nm} [i \bmod 2 = 0] C_{nm}^{i} odd^{i} even^{nm-i}$$

$$\dfrac{(odd + even)^{nm} + (odd - even)^{nm}}{2}$$

由于 $n,m$ 同阶，时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998'244'353;
long long n,m,l,r;
Mint<mod> ans;
int main(){
    cin>>n>>m>>l>>r;
    Mint<mod> odd=(r-l+1)/2;
    Mint<mod> even=(r-l+1)/2;
    if((r-l+1)%2==1){
        if(l%2==1) ++odd;
        else ++even;
    }
    if((n*m)%2==0) ans=((odd+even).multiply(n*m)+(odd-even).multiply(n*m))/2;
    else ans=(odd+even).multiply(n*m)-((odd-even).multiply(n*m)+(even-odd).multiply(n*m))/2;
    cout<<ans<<'\n';
    return 0;
}