专栏文章

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

EExFish
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzk5e5
此快照首次捕获于
2025/12/01 18:07
3 个月前
此快照最后确认于
2025/12/01 18:07
3 个月前
查看原文
你首先考虑到 n×mn\times m 为奇数的情况，显然这个时候点 xx 个为奇数的话就可以补全剩余的，否则就补齐本身。容易得出这样任意解都是对的。然后考虑剩余的，直接组合数可以得出公式 (r−l+1)nm+(r−l+1) mod 22\frac{(r-l+1)^{nm}+(r-l+1)\bmod 2}{2}。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...