E. Height All the Same

E. Height All the Same

题目大意：

给你一个n*m 的矩阵，让你在里面填数字代表这个位置的高度，数字的范围是[L,R]，有两种操作，第一种就是给一位置的高度加2，第二种就是给两个相邻的位置都加1。

求：填完数字，经过若干次两种操作之后可以使得高度相同的填数字方案数是多少？

题解：

其实这个题目最好自己先慢慢想，如果你水平在蓝名接近紫名了，这个应该是可以自己想出来的。

• 首先你会发现无论怎么填数字，因为可以在任意一个位置增加任意数量的2，所以所有的数字对2取模，最后都会变成一个01的矩阵，所以就转化为一个01矩阵怎么让其变成全为0或者全为1。

• 这时候就看第二种操作，会发现这个就是让相邻的两个位置取反。

• 如果我想消去一个1，则需要相邻有1的存在，消去0同理。如果1没有相邻的1，那么它不会改变1或0的数量，这个时候进行第二个操作的本质是在移动这个1的位置，这一点需要理解。

• 最后你会发现只要是1或者0是偶数个就一定有解。

• 如果1是偶数个，则可以把偶数个1移动到一起，然后两两消去变成0。如果0是偶数个同理。

• 所以如果要有解，那么填完数字之后，奇数的数量或者偶数的数量要有一个是偶数。

• 所以如果n*m 是一个奇数，因为 奇数=奇数+偶数，所以肯定有解，所以每一个位置可以在 [L,R] 的范围内任意取值，所以答案就是 \((R-L+1)^{nm}\)

• 如果是 n*m 是一个偶数，设偶数个数为x，奇数个数为y。

  则答案应该是 \(C_{nm}^{0}x^{nm}+C_{nm}^{2}x^{nm-2}y^2+C_{nm}^{4}x^{nm-4}y^4...\) 枚举所有的偶数，但是这个不好求啊，高中数学要是学得好应该还是可以想到办法的，因为这个式子的求法高中是学习过的。

  上面的式子就等价于 \((x+y)^{nm}-(x-y)^{nm}\) 这个可以自己推一下，很简单。

做完之和会发现这个其实并不是很难，但是呢，如果可以自己独立完成还是很有成就感的，这种自己有一点思路的题目还是建议尽量独立思考，也许花的时间会比较长，但是对思维能力的提升会快一些。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn=2e4+10;
const int mod=998244353;
typedef long long ll;
long long binpow(long long x,long long b)
{
    long long ans=1;
    while(b){
        if (b&1) ans=ans*x%mod;
        x=x*x%mod;
        b>>=1;
    }
    return ans;
}
long long inv(long long x,long long mod)
{
    long long k=mod-2,ans=1;
    while(k)
    {
        if (k&1) ans=ans*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return ans;
}
 
int main(){
    ll n,m,l,r;
    scanf("%lld%lld%lld%lld",&n,&m,&l,&r);
    ll x=r-l+1,b=n*m;
    ll ans=binpow(x,b);
    if(b%2==0) ans=(ans+(x&1))*inv(2,mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

E. Height All the Same

原文：https://www.cnblogs.com/EchoZQN/p/12684675.html