CF2048G Kevin and Matrices 题解

先考虑

\min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)\lt \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right)

的情况。此时需要满足，存在

x

使得存在一行都小于

x

，且存在一列都大于等于

x

。显然这两个条件无法同时满足，故这种情况不存在。

接下来考虑

\min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)= \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right)

的情况。设这个值等于

k

，那么相当于要求：

存在一行的最大值等于 $k$ ，且每一行的最大值都大于等于 $k$ ；
存在一列的最小值等于 $k$ ，且每一列的最小值都小于等于 $k$ 。

设此时的答案为

ans_k

，

f(a,b)

表示每一行的最大值都大于等于

a

且每一列的最小值都小于等于

b

的方案数，那么做一个二维差分即可得到：

ans_k=f(k,k)-f(k+1,k)-f(k,k-1)+f(k+1,k-1)

于是问题转化为了如何求

f(a,b)

。

考虑容斥：

钦定 $i$ 行的最大值都小于 $a$ ；
对于每一列：
- 先不考虑列的限制，方案数为 $v^{n-i}(a-1)^i$ ；
- 再减掉这一列的最小值大于 $b$ 的方案数，于是需要减去 $(v-b)^{n-i}(\max(a-b-1,0))^i$ ；
由于每一列是等价的，所以其对答案的贡献为：

(-1)^i{n\choose i}\left(v^{n-i}(a-1)^i-(v-b)^{n-i}(\max(a-b-1,0))^i\right)^m

这里我们认为

0^0=1

。预处理组合数后枚举

i

并快速幂计算即可。

时间复杂度

\mathcal O(nv \log m)

。

const int N=1e6+5,mod=998244353;
int n,m,v,fac[N],infac[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1;
		a=1ll*a*a%mod;
	}
	return res;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
void init(int n){
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
}
int C(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int f(int a,int b){
	int res=0;
	for(int i=0;i<=n;i++){
		int val=ad(1ll*ksm(v,n-i)*ksm(a-1,i)%mod,mod-1ll*ksm(v-b,n-i)*ksm(max(a-b-1,0),i)%mod);
		int ans=1ll*C(n,i)*ksm(val,m)%mod;
		if(i&1) add(res,mod-ans);
		else add(res,ans);
	}
	return res;
}
void solve(){
	cin>>n>>m>>v;
	init(n);
	int ans=0;
	for(int k=1;k<=v;k++) add(ans,(0ll+f(k,k)-f(k+1,k)-f(k,k-1)+f(k+1,k-1)+mod+mod)%mod);
	cout<<ans<<endl;
}

CF2048G Kevin and Matrices 题解

文章操作

相关推荐

评论

CF2048G Kevin and Matrices 题解