题解：AT_arc230_d [ARC230D] Min Max Matrix

· · 题解

更好的阅读体验

几步最关键的观察我场上都做出来了，可是为什么就差那么一点点呢！

下文中 n, m, V 分别是原题中的 H, W, M。

翻译一下题目说的条件：每行最大值的最小值，等于每行最小值的最大值。假设这个值为 x。那么必然存在至少一行全部 \le x，且存在至少一列全部 \ge x。由于这一行、这一列一定有一个交点，因此交点处的取值必然 =x。

接下来我们发现如果这个 x 存在，那么它必然是唯一的。假设有多个满足条件的 x，如 a_{i, j} = x_1, a_{k, l} = x_2。那么若 x_1 < x_2，那么 x_1 = a_{i, j} \ge a_{i, l} \ge a_{k, l} = y，矛盾；x_1 > x_2 的话也能同理推出矛盾。

也就是说，所有合法的矩阵可以通过 x 的不同取值来分类。只需要对于每个 x 分别求出合法的矩阵数量再求和即可。

考虑容斥：我们现在钦定 i 行 \le x，钦定 j 列 \ge x。那么有 ij 个格子的取值只能 =x，有 i (m - j) 个格子的取值 \le x，有 j (n - i) 个格子的取值 \ge x，还有 (n-i)(m-j) 个格子无限制，再乘上钦定 i 行，j 列的方案数，因此方案数就是 \displaystyle{{n \choose i} {m \choose j}V^{(n-i)(m-j)} \cdot x ^{i (m - j)} \cdot (V - x + 1)^{j (n - i)}}。

假设钦定 i 行 j 列的结果是 f_{x, i, j}，那么你打个表或者观察一下容斥系数可以发现，答案是

\sum_{i = 1}^n \sum _{j=1}^m \sum_{x = 1}^V (-1)^{i + j} f_{x, i, j}

这个是难以直接求解的。考虑把 f 带进去。

\begin{align} \text{answer} &= \sum_{i = 1}^n \sum _{j=1}^m \sum_{x = 1}^V (-1)^{i + j} {n \choose i} {m \choose j}V^{(n-i)(m-j)} \cdot x ^{i (m - j)} \cdot (V - x + 1)^{j (n - i)} \nonumber \\ &= \sum_{x=1}^V\sum_{i = 1}^n {n \choose i}(-1)^i \sum_{j = 1}^m (-1)^j {m \choose j} \left[(V-x+1)^{n-i}\right]^j \cdot \left[V^{n-i} \cdot x^i\right]^{m - j}\nonumber \\ &= \sum_{x=1}^V\sum_{i = 1}^n {n \choose i}(-1)^i \left(\sum_{j = 0}^m (-1)^j {m \choose j} \left[(V-x+1)^{n-i}\right]^j \cdot \left[V^{n-i} \cdot x^i\right]^{m - j} - \left[V^{n-i} \cdot x^i\right]^{m}\right)\nonumber \\ &= \sum_{x=1}^V \sum_{i=1}^n {n \choose i}(-1)^i \left(\left(V^{n-i} \cdot x^i - (V-x+1)^{n-i}\right) ^ m- \left[V^{n-i} \cdot x^i\right]^{m}\right) \nonumber \end{align}

我们把和 x 有关的部分可以看作一个关于 x 的函数，所求即为该函数的一个前缀和。注意到这个前缀和函数必然是一个多项式，且次数为 O(nm)。所以这个多项式的一个点值可以用拉格朗日插值求出。由于我们可以选择连续的点值进行差值，因此求值的过程可以做到 O(nm)。

至此问题在 O(V+n^2 m \log P) 的时间内得到解决，其中第一部分来源于阶乘和逆元，第二部分来源于求 O(nm) 个点值。

#include<bits/stdc++.h>
#define endl '\n'
#define N 206
#define M 100000006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int n,m,V,fac[M],ifac[M],ans,y[N*N];
int qpow(int x,int y=MOD-2)
{
  int ret=1;
  for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
  return ret;
}
int binom(int x,int y) {return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
main()
{
  scanf("%d%d%d",&n,&m,&V),fac[0]=1;
  for(int i=1;i<M;i++)fac[i]=1ll*i*fac[i-1]%MOD;
  ifac[M-1]=qpow(fac[M-1]);
  for(int i=M-2;~i;i--)
    ifac[i]=1ll*(i+1)*ifac[i+1]%MOD;
  for(int k=0;k<=n*m;k++)
    for(int i=1;i<=n;i++)
    {
      int sum=(qpow((1ll*qpow(k,i)*qpow(V,n-i)%MOD-qpow((V+1-k+MOD)%MOD,n-i)+MOD)%MOD,m)-
               qpow(1ll*qpow(k,i)*qpow(V,n-i)%MOD,m)+MOD)%MOD;
      if(i&1)dec(y[k],1ll*sum*binom(n,i)%MOD%MOD);
      else add(y[k],1ll*sum*binom(n,i)%MOD%MOD);
    }
  for(int k=1;k<=n*m;k++)add(y[k],y[k-1]);
  if(V<=n*m)ans=y[V];
  else {
    for(int i=0;i<=n*m;i++)
      if((n*m-i)&1)dec(ans,1ll*y[i]*fac[V]%MOD*ifac[V-n*m-1]%MOD*
                       ifac[V-i]%MOD*fac[V-i-1]%MOD*ifac[i]%MOD*ifac[n*m-i]%MOD);
      else add(ans,1ll*y[i]*fac[V]%MOD*ifac[V-n*m-1]%MOD*
               ifac[V-i]%MOD*fac[V-i-1]%MOD*ifac[i]%MOD*ifac[n*m-i]%MOD);
  }
  dec(ans,y[0]);
  printf("%d\n",ans);
  return 0;
}