QOJ #3082. Ascending Matrix 题解

Description

给定整数 $N, M, K, R, C, V$。求满足以下所有条件的 $N \times M$ 整数矩阵 $a = (a_{i,j})$ 的数量，并对结果取模 $998244353$。

• 对所有 $1 \leq i \leq N,\, 1 \leq j \leq M$，有 $1 \leq a_{i,j} \leq K$。
• 对所有 $1 \leq i \leq N,\, 1 \leq j \leq M-1$，有 $a_{i,j} \leq a_{i,j+1}$。
• 对所有 $1 \leq i \leq N-1,\, 1 \leq j \leq M$，有 $a_{i,j} \leq a_{i+1,j}$。
• 并且满足 $a_{R,C} = V$。

$1\leq N,M\leq 200,1\leq K\leq 100$。

Solution

（注：这里 $R$ 和 $C$ 默认都先减了 $1$）

首先这题不太好直接计数，考虑转格路后用 LGV 引理计数。

先找到数值 $\leq i$ 和 $>i$ 的分界线 $L_i$，这是个从 $(0,m)$ 到 $(n,0)$ 的方向只有左下的路径。

需要满足 $L_i$ 完全在 $L_{i+1}$ 的左上，但是可以有交点重合，那么将 $L_i$ 向右下平移 $i-1$ 步后就不会有交点了。

也就是说第 $i$ 个起点为 $(i-1,m+i-1)$，第 $i$ 个终点为 $(n+i-1,i-1)$，要求这 $k-1$ 个路径不能有交。

然后去满足 $a_{r,c}=v$ 的限制。

这时需要满足前 $v-1$ 条路径需要经过 $(r+v-2,c+v-2)$ 的左上角，且第 $v$ 条路径需要经过 $(r+v,c+v)$ 的右下角。

如果对前 $v-1$ 和后 $k-v$ 条路径按照不同的方式计数的化就不能用 LGV 引理进行容斥了，考虑统一标准。

容易发现它们都不能经过 $(r+v-1,c+v-1)$，那么可以把 $(r+v-1,c+v-1)$ 删掉，问题变为满足不交限制之后要求经过 $(r+v-2,c+v-2)$ 左上角的路径需要有恰好 $v-1$ 条。

令 $a_{i,j}$ 表示从第 $i$ 个起点走到第 $j$ 个终点，且不经过 $(r+v-2,c+v-2)$ 左上角的方案数；$b_{i,j}$ 表示从第 $i$ 个起点走到第 $j$ 个终点，且经过 $(r+v-2,c+v-2)$ 左上角的方案数。然后跑 $w_{i,j}=a_{i,j}+b_{i,j}x$ 的行列式，要求出第 $v-1$ 次系数。

插值维护即可。

时间复杂度：$O(n^3+k^4)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 205, kMaxK = 105, kMaxL = 305, kMod = 998244353;

int n, m, k, r, c, v;
int f[kMaxL][kMaxL][2], w[kMaxK][kMaxK][2], val[kMaxK], ww[kMaxK][kMaxK];

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void get(int det) {
  memset(f, 0, sizeof(f));
  f[det][m + det][det <= r + v - 2 && m + det <= c + v - 2] = 1;
  for (int i = det; i <= n + k - 1; ++i) {
    for (int j = m + det; ~j; --j) {
      if (i == r + v - 1 && j == c + v - 1) continue;
      int op = (i <= r + v - 2 && j <= c + v - 2);
      if (i) {
        for (int lst = 0; lst <= 1; ++lst) inc(f[i][j][lst | op], f[i - 1][j][lst]);
      }
      for (int lst = 0; lst <= 1; ++lst) inc(f[i][j][lst | op], f[i][j + 1][lst]);
    }
  }
  for (int i = 0; i < k - 1; ++i) w[det + 1][i + 1][0] = f[n + i][i][0], w[det + 1][i + 1][1] = f[n + i][i][1];
}

int getdet(int n) {
  int ret = 1;
  for (int i = 1; i <= n; ++i) {
    if (!ww[i][i]) {
      for (int j = i + 1; j <= n; ++j) {
        if (ww[j][i]) {
          std::swap(ww[i], ww[j]), ret = sub(0, ret);
          break;
        }
      }
    }
    if (!ww[i][i]) return 0;
    ret = 1ll * ret * ww[i][i] % kMod;
    for (int j = i + 1; j <= n; ++j) {
      int d = 1ll * ww[j][i] * qpow(ww[i][i]) % kMod;
      for (int k = i; k <= n; ++k) dec(ww[j][k], 1ll * ww[i][k] * d % kMod);
    }
  }
  return ret;
}

int lagrange(int v) {
  int ret = 0;
  for (int i = 1; i <= k; ++i) {
    static int f[kMaxK];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    int coef = val[i];
    for (int j = 1; j <= k; ++j) {
      if (i == j) continue;
      coef = 1ll * coef * qpow(sub(i, j)) % kMod;
      for (int s = k - 1; ~s; --s) {
        f[s] = 1ll * f[s] * (kMod - j) % kMod;
        if (s) inc(f[s], f[s - 1]);
      }
    }
    inc(ret, 1ll * coef * f[v] % kMod);
    // std::cerr << ret << ' ' << 1ll * coef * f[v] % kMod << '\n';
  }
  return ret;
}

void dickdreamer() {
  std::cin >> n >> m >> k >> r >> c >> v; --r, --c;
  for (int i = 0; i < k - 1; ++i) get(i);
  // for (int i = 1; i <= k - 1; ++i) {
  //   for (int j = 1; j <= k - 1; ++j) {
  //     std::cerr << w[i][j][0] << " \n"[j == k - 1];
  //   }
  // }
  // for (int i = 1; i <= k - 1; ++i) {
  //   for (int j = 1; j <= k - 1; ++j) {
  //     std::cerr << w[i][j][1] << " \n"[j == k - 1];
  //   }
  // }
  for (int i = 1; i <= k; ++i) {
    for (int x = 1; x <= k - 1; ++x)
      for (int y = 1; y <= k - 1; ++y)
        ww[x][y] = add(w[x][y][0], 1ll * i * w[x][y][1] % kMod);
    val[i] = getdet(k - 1);
  }
  std::cout << lagrange(v - 1) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}