coderforces-Round-630-Div-2-E

题目意思

就是给一个矩阵的大小，以及一个区间l~R，现在可以给相邻两个方格+1或者一个方格+2，你可以在矩阵上任意放l~r的高度的方块，使得他们的高度相等，求放方块的方案数

思路

因为相邻两块可以放，所以可以推出任意两块我们是可以修改他们的奇偶性的，根据对称性可以很简单的写出来
首先当nm%2==1的时候答案肯定是$(R-L+1)^nm$,因为肯定存在一个行或者列为奇数，另一个为偶数，这样就能任意把两个格子的奇偶性质互换了，所以可以随便填，我都可以根据后期来改变。
当nm%2==0的时候，考虑从nm的方格中取出2,4,6,8,10···，偶数个格子放奇数，另外的放偶数，只有这样是可以的，因为他们都要成双成对才行，于是我们得到一个答案
令a为偶数的个数，b为奇数的个数，然后得到答案

$$\begin{aligned} &C_{nm}^i a^ib^{nm-i}(i\&1==0)\\ &=\frac{(a+b)^{nm}+(a-b)^{nm}}{2} \end{aligned}$$

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 998244353;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
	int n,m,l,r;
	scanf("%d %d %d %d",&n,&m,&l,&r);
	int x=r-l+1;
	if(1ll*n*m%2==1)printf("%lld\n",quick_pow(x,1ll*n*m));
	else{
		if(x%2==0)printf("%lld\n",quick_pow(x,1ll*n*m)*inv(2)%mod);
		else printf("%lld\n",(quick_pow(x,1ll*n*m)+1)*inv(2)%mod);
	} 
}