【0】做题心得 - 2025 NOIP #70 - T4【容斥】【组合数学】

ExFish · 2025-11-27 16:46:10 · 题解

你首先考虑到 n\times m 为奇数的情况，显然这个时候点 x 个为奇数的话就可以补全剩余的，否则就补齐本身。容易得出这样任意解都是对的。然后考虑剩余的，直接组合数可以得出公式 \frac{(r-l+1)^{nm}+(r-l+1)\bmod 2}{2}。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=998244353;
ll qp(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=(a*a)%P)
        if(b&1) res=(res*a)%P;
    return res; 
}
ll n,m,l,r;
int main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>l>>r;
    if((n*m)&1) cout<<qp(r-l+1,n*m);
    else cout<<(qp(r-l+1,n*m)+(r-l+1)%2)%P*qp(2,P-2)%P;
    return 0;
}