题目大意
You want to walk from \((0,0, \ldots, 0)\) to \(\left(a_0, a_1, \ldots, a_{n-1}\right)\) in an \(n\)-dimensional space. On each step, you can increase one component of your coordinate vector by one. There are \(m\)obstacles \(p_1, p_2, \ldots, p_m\). You want to find the number of paths that don't pass through the obstacles.
However, this problem is too simple for an ICPC contest in the year 8102. We add one more constraint. For every point \(\left(x_0, x_1, \ldots, x_{n-1}\right)\) on your path, the components of this vector should be non-decreasing: \(x_0 \leq x_1 \leq \ldots \leq x_{n-1}\).
Output the number of paths modulo \(10^9+7\).
The first line contains two integers \(n\) and \(m(1 \leq n \leq 50,0 \leq m \leq 50)\).
The second line contains \(n\) integers \(a_0, a_1, \ldots, a_{n-1}\left(0 \leq a_0 \leq a_1 \leq \ldots \leq a_{n-1} \leq 10^4\right)\), the coordinate vector of your destination.
The following \(m\)lines describe obstacles. The \(i\)-th of these lines contains \(n\) integers \(p_{i, 0}, p_{i, 1}, \ldots, p_{i, n-1} \left(0 \leq p_{i, 0} \leq p_{i, 1} \leq \ldots \leq p_{i, n-1} \leq 10^4\right)\), the coordinate vector of an obstacle.
The starting point, destination, and all the obstacles are distinct.
Output the answer modulo \(10^9+7\).
题解
我们先将 \(a_i\) 不严格递增转换一下。设 \(b_i = a_i + i\)，问题转化成从 \((1, 2, \cdots, n)\) 到 \((b_1, b_2, \cdots, b_n)\) 且中途 \(x_i\) 保持严格递增的方案数。
引理 \(1\)：不考虑 \(x_i\) 严格递增的限制，此时从 \((s_1, s_2, \cdots, s_n)\) 走到 \((c_1, c_2, \cdots, c_n)\) 的方案数是 \(\binom{\sum c_i - s_i}{c_1-s_1, c_2 - s_2, \cdots, c_n - s_n} = (\sum c_i - s_i)! \times \prod\dfrac{1}{(c_i - s_i)!}\) 。
下标严格递增可以表示为网格图的形式。我们将第 \(i\) 个维度视为一条从 \((0, i)\) 到 \((\sum (b_i - i), b_i)\) 的路径，这条路径只能向右 / 向右上走。我们将向右上视为 \(+1\)，向右视为不变，那么会有如下条件。
- 由于每次只能移动相邻一格，因此每一步只能有一条路径向右上，其他路径向右。
- 由于中途 \(x_i\) 要保持递增，因此每条路径都应该互不相交。
引入 LGV 引理。
设 \(w(P)\) 为路径 \(P\) 上的边权之积，\(e(u, v)\) 表示 \(u\) 到 \(v\) 每一条路径 \(P\) 的 \(w(P)\) 之和，起点、终点的点集为 \(A, B\)。那么有：
\[M = \begin{bmatrix} e(A_1, B_1) & e(A_1, B_2) & \cdots & e(A_1, B_n)\\ e(A_2, B_1) & e(A_2, B_2) & \cdots & e(A_2, B_n)\\ \vdots & \vdots & \ddots & \vdots \\ e(A_n, B_1) & e(A_n, B_2) & \cdots & e(A_n, B_n)\\ \end{bmatrix}\\ \begin{aligned} \text{det}(M) = & \sum_{{\substack{S: A \to B \\ S \text{为不相交路径组}}}} \text{sgn}(\sigma(S)) \prod_{i=1}^{n} \omega(S_i)\\ \iff \sum_{\sigma} \text{sgn}(\sigma) \prod_{i = 1}^n e(A_i, B_{\sigma_i}) = & \sum_{{\substack{S: A \to B \\ S \text{为不相交路径组}}}} \text{sgn}(\sigma(S)) \prod_{i=1}^{n} \omega(S_i) \end{aligned} \]
引入一个平凡的 LGV 引理的推论。
设 \(g(S)\) 为该路径组的权值，设 \(f(\sigma)\) 为 \(A_i \to B_{\sigma_i}\) 的所有路径组的权值之和。
\[\begin{aligned} \sum_{\sigma} \text{sgn}(\sigma) \prod_{i = 1}^n e(A_i, B_{\sigma_i}) = & \sum_{{\substack{S: A \to B \\ S \text{为不相交路径组}}}} \text{sgn}(\sigma(S)) \prod_{i=1}^{n} \omega(S_i)\\ \iff \sum_{\sigma} \text{sgn}(\sigma) f(\sigma) = & \sum_{{\substack{S: A \to B \\ S \text{为不相交路径组}}}} \text{sgn}(\sigma(S)) g(S)\\ \end{aligned} \]
回到原题。我们设推论中的 \(g(S)\) 表示路径组 \(S\) 是否满足以上两个条件，\(f(\sigma)\) 就是所有 \(S: (0, i) \to (\sum(b_{\sigma_i} - \sigma_i), b_{\sigma_i})\) 的 \(g(S)\) 之和。由引理 \(1\)，\(f(\sigma) = (\sum b_{\sigma_i} - i)! \times \prod\dfrac{1}{(b_{\sigma_i} - i)!}\)。
考虑一个路径组 \(S\)。由于这个路径起终点和网格图的特殊性，当 \(\sigma(S)\) 逆序对大于 \(0\) 时，\(S\) 一定会相交。因此，对于所有 \(\sigma(S)\) 逆序对大于 \(0\) 的 \(S\)，使得 \(g(S) = 0\)。
设 \(A_i = (0, i), B_i = (\sum(b_{i} - i), b_{i})\)。那么，就有：
将 \(M\) 的行列式求出即可。