CF1332E Height All the Same 题解

wing_heart · 2025-11-27 15:55:27 · 题解

可以用生成函数和多项式取模做。本质上和矩阵乘法差不多，但是更好写。

观察发现，若所有位置奇偶性相同，则用操作二可以做到合法。操作一可以看作反转相邻两个位置的奇偶性。

当且仅当奇数高度位置的个数为奇数个，且偶数高度位置的个数为奇数个，无解。否则有解。

按照 n \times m 的奇偶性分类讨论。只有 2 \mid n \times m 时可能出现上述无解情况。

只需要求，n \times m 个位置，每个位置可以填 A 种奇数，或者 B 种偶数。求 填奇数的位置 有偶数个，的方案数。

生成函数 f(x) = ax+b，[x^1] 表示 填奇数的位置 有奇数个的方案数，[x^0] 表示 填奇数的位置 有偶数个的方案数。

需要求 [x^0] (Ax+B)^{n\times m} \pmod{x^2-1}。注意是多项式取模。

其实不需要会多项式取模，只是在多项式快速幂的过程中，把 x^2 换成 x^0。因为 0,2 奇偶性相同。

不用动脑子而且比矩阵好写一点。

#include<bits/stdc++.h>
#define sf scanf 
#define pf printf 
#define rep(x,y,z) for(int x=y;x<=z;x++) 
#define per(x,y,z) for(int x=y;x>=z;x--) 
using namespace std;
typedef long long ll;
namespace wing_heart {
    constexpr int mod=998244353;
    struct modint {
        int x;
        modint (int y=0) : x(y) {} 
        modint operator + (modint b) const { return x+b.x<mod ? x+b.x : x+b.x-mod; }
        modint operator * (modint b) const { return 1ll*x*b.x%mod; }
        modint &operator += (modint b) { return *this = *this + b; } 
        modint &operator *= (modint b) { return *this = *this * b; } 
    };
    modint ksm(modint a,ll b) {
        modint s=1;
        while(b) {
            if(b&1) s*=a;
            a*=a;
            b>>=1;
        }
        return s;
    }
    struct poly {
        modint x1,x0;
        poly operator + (poly b) const { return {x1+b.x1,x0+b.x0}; }
        poly operator * (poly b) const { return {x1*b.x0+x0*b.x1,x0*b.x0+x1*b.x1}; }
        poly &operator += (poly b) { return *this = *this + b; }
        poly &operator *= (poly b) { return *this = *this * b; }
    };
    poly ksm_poly(poly a,ll b) {
        poly s = {0,1};
        while(b) {
            if(b&1) s*=a;
            a*=a;
            b>>=1;
        }
        return s;
    }
    int n,m,l,r;
    int A,B;
    int solve() {
        poly t = ksm_poly({A,B},1ll*n*m);
        return t.x0.x;
    }
    void main() {
        sf("%d%d%d%d",&n,&m,&l,&r);
        if((1ll*n*m)&1) pf("%d\n",ksm(r-l+1,1ll*n*m).x), exit(0);
        if((l&1)^(r&1)) A=B=(r-l+1)>>1;
        else if(l&1) A=(r-l+2)>>1, B=(r-l)>>1;
        else A=(r-l)>>1, B=(r-l+2)>>1;
        pf("%d\n",solve());
    }
}
int main() {
    wing_heart :: main();
}