[ARC230D] Min Max Matrix

· · 题解

或许更好的阅读体验。

演都不演了？arc 搬原？？？

思路：

首先不难发现左边恒大于等于右边。

考虑对于 i, j，有 R_i \ge A_{i, j} \ge C_j。

于是只要右边小于等于左边即可；枚举这个式子的值，设为 k，那么显然只要存在一行都 \le k，存在一列都 \ge k 就合法。

直接二维二项式反演一下，容斥钦定有 i 行 \le k 有 j 列 \ge k，那么显然方案数 k^{i(m - j)} (w - k + 1)^{j (n - i)} w^{(n - i)(m - j)}，于是答案是：

\sum_{k = 1}^w \sum_{i = 1}^n \sum_{j = 1}^m (-1)^{i + j} \binom{n}{i} \binom{m}{j} k^{i(m - j)} (w - k + 1)^{j (n - i)} w^{(n - i)(m - j)}

原题 cf 因为 m 特别大，所以可能容易想到；但是 arc 那题 n, m 同阶的，看到这个式子第一想法不是把 k 相关挪到后面考虑能不能快速算吗？？？然后卡了 O(n^4) 挺久，才发现这后面可以二项式定理！

具体的，注意到后面那个式子是：

\sum_{j = 1}^m (-1)^j \binom{m}{j} \left( (w - k + 1)^{n - i}\right)^j (k^i w^{n - i})^{m - j}

令 A = k^i w^{n - i}, B = (w - k + 1)^{n - i}，那么上面式子是：

(A - B)^m - A^m

所以枚举 k 和 i 复杂度就是 O(nv \log n) 了。

然后再发现答案关于 w 是一个不超过 nm 的多项式，所以算出前面 nm 项的点值然后拉插即可，时间复杂度为 O(n^2 m \log n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
const int N = 4e4 + 10, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
} 
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline void getdec(int &x, int y){
    x = (x < y) ? (x - y + mod) : (x - y);
}
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int T, n, m, w, ans;
int fac[N], ifac[N], p1[N], p2[N], pp[N], y[N];
inline void init(){
    fac[0] = fac[1] = 1;
    for(int i = 2; i < N; ++i)
      fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N - 1] = qpow(fac[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; --i)
      ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
}
inline int binom(int n, int m){
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
namespace Lacha{
    int pre[N], suf[N];
    inline int getf(int n, int k){
        pre[0] = 1;
        for(int i = 1; i <= n; ++i)
          pre[i] = 1ll * (k - i + mod) % mod * pre[i - 1] % mod;
        suf[n + 1] = 1;
        for(int i = n; i >= 0; --i)
          suf[i] = 1ll * (k - i + mod) % mod * suf[i + 1] % mod;
        int ans = 0, now = 0;
        for(int i = 1; i <= n; ++i){
            int sum = 1ll * pre[i - 1] * suf[i + 1] % mod * ifac[i - 1] % mod * ifac[n - i] % mod * y[i] % mod;
            if((n - i) & 1)
              ans = (ans - sum + mod) % mod;
            else
              ans = (ans + sum) % mod;
       }
       return ans;
    }
};
inline void solve(){
    ans = 0;
    n = read(), m = read(), w = read();
    pp[0] = 1;
    for(int i = 1; i <= n; ++i)
      pp[i] = 1ll * w * pp[i - 1] % mod;
    for(int k = 1; k <= n * m + 2; ++k){
        p1[0] = p2[0] = 1;
        int a = k, b = w - k + 1;
        for(int i = 1; i <= n; ++i)
          p1[i] = 1ll * p1[i - 1] * a % mod, p2[i] = 1ll * p2[i - 1] * b % mod;
        for(int i = 1; i <= n; ++i){
            int A = 1ll * p1[i] * pp[n - i] % mod, B = p2[n - i];
            int sum = 1ll * (qpow((A - B + mod) % mod, m) - qpow(A, m) + mod) % mod * binom(n, i) % mod;
            if(i & 1)
              getdec(ans, sum);
            else
              getadd(ans, sum);
        }
        y[k] = ans;
    }
    write(Lacha::getf(n * m + 2, w));
    putchar('\n');
}
int main(){
    init();
    T = 1;
    while(T--)
      solve();
    return 0;
}