CF2048G Kevin and Matrices 题解

Coffee_zzz · 2025-10-10 21:33:38 · 题解

先考虑 \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 的方案数，那么做一个二维差分即可得到：

于是问题转化为了如何求 f(a,b)。

考虑容斥：

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

这里我们认为 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;
}