C、Cells

题目大意

你有一张无穷大的二维矩阵，你的出发点在格点 $(0,a_i)$ ，并且保证了出发点横坐标依次递增： $a_i<a_{i+1}$ 。

你的目标点分别是 $(1,0),(2,0)...(n,0)$ ，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。

Solution

考点：LGV引理+多项式卷积

这题第一个难点就是要会转换模型，他的方案数本质上就是一个LGV引理的模板。

稍微提一下LGV引理，它讲的就是你有起点 $(A_1,A_2...A_n)$ ，目标点 $(B_1,B_2...B_n)$ ，那么你从 $n$ 个起点出发经过完全不相交的边去到 $n$ 个终点的方案数会等于下面的行列式。

$M= \left| \begin{array}{cccc} 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{array} \right|$

$e(A_1,B_1)$ 对应的是从 $A_1$ 去往 $B_1$ 的方案数，那么对应到本题，从 $a_1$ 去往 $(1,0)$ 的方案数就是经典过河卒问题，它的方案数应该是 $C_{a_1+1}^1$ 。

写出本题的行列式：

$M= \left| \begin{array}{cccc} C_{a_1+1}^{1} & C_{a_1+2}^{2} & \cdots & C_{a_1+n}^{n} \\ C_{a_2+1}^{1} & C_{a_2+2}^{2} & \cdots & C_{a_2+2}^{n} \\ \vdots & \vdots & \ddots & \vdots \\ C_{a_n+1}^{1} & C_{a_n+2}^{2} & \cdots & C_{a_n+n}^{n} \\ \end{array} \right|$

求解 $n$ 阶方阵的常用做法是高斯消元，但是很明显 $O(n^3)$ 的做法无法通过此题，我们要对这个有特点的行列式做一些初等变换。

我们把这个方阵里面的组合数用阶乘的方式打开，可以得到下面的行列式。

$M= \left| \begin{array}{cccc} \frac{(a_1+1)!}{1!a_1!} & \frac{(a_1+2)!}{2!a_1!} & \cdots & \frac{(a_1+n)!}{n!a_1!} \\ \frac{(a_2+1)!}{1!a_2!} & \frac{(a_2+2)!}{2!a_2!} & \cdots & \frac{(a_2+n)!}{n!a_2!} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{(a_n+1)!}{1!a_n!} & \frac{(a_n+2)!}{2!a_n!} & \cdots & \frac{(a_n+n)!}{n!a_n!} \\ \end{array} \right|$

我们发现第 $i$ 列都有 $\frac{1}{i!}$ 我们把他提出外面去得到：

$M=\prod\limits_{i=1}^n\frac{1}{i!} \left| \begin{array}{cccc} \frac{(a_1+1)!}{a_1!} & \frac{(a_1+2)!}{a_1!} & \cdots & \frac{(a_1+n)!}{a_1!} \\ \frac{(a_2+1)!}{a_2!} & \frac{(a_2+2)!}{a_2!} & \cdots & \frac{(a_2+n)!}{a_2!} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{(a_n+1)!}{a_n!} & \frac{(a_n+2)!}{a_n!} & \cdots & \frac{(a_n+n)!}{a_n!} \\ \end{array} \right|$

接下来就要作过一定线性代数的题了，要认出这是一个范德蒙德行列式。

具体我们也能推出来，我们假设取了第一行的前三列，我们可以得出下面的这个行列式。

$\left| \begin{array}{cccc} (a_1+1) & (a_1+1)*(a_1+2) & (a_1+1)*(a_1+2)*(a_1+3) \end{array} \right|$

为了好看我们转置一下，并且要知道行列式转置值不变，我们得出下面的这个三行一列行列式，本质上和上面的是一样的。

$\left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)*(a_1+2) \\ (a_1+1)*(a_1+2)*(a_1+3) \end{array} \right|$

我们接下来做行初等变换，第二行乘以 $-2$ 加到第三行上去，得到

$\left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)*(a_1+2) \\ (a_1+1)^2*(a_1+2) \end{array} \right|$

接下来用第一行乘以 $-(a_1+1)$ 加到第三行上去，这样我们就得到

$\left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)*(a_1+2) \\ (a_1+1)^3 \end{array} \right|$

接着用第一行乘以 $-1$ 加到第二行计算到

$\left| \begin{array}{cccc} (a_1+1) \\ (a_1+1)^2 \\ (a_1+1)^3 \end{array} \right|$

这样一个范德蒙德行列式就出来了，我们再把转置之后的行列式每一列提出一个 $(a_i+1)$ 就变成了标准的范德蒙德行列式。

$M=\prod\limits_{i=1}^n\frac{a_i+1}{i!} \left| \begin{array}{cccc} 1 & 1 & \cdots & 1 \\ (a_1+1) & (a_2+1) & \cdots & (a_n+1) \\ \vdots & \vdots & \ddots & \vdots \\ (a_1+1)^{n-1} & (a_2+1)^{n-1} & \cdots & (a_n+1)^{n-1} \\ \end{array} \right| =\prod\limits_{i=1}^n(\frac{a_i+1}{i!}\prod\limits_{1\le i<j\le n}(a_j-a_i))$

对于后面那个 $\prod\limits_{1\le i<j\le n}^n a_j-a_i$ ，可以比较自然的想到用多项式乘法计算个数。

构造 $f(x)=\sum x^{-a_i},g(x)=\sum x^{a_j}$

那么我们把 $f(x)*g(x)$ 卷积之后得到的 $F(x)=\sum c_i*x^i$ ，它的每个指数 $i$ 对应着一个 $a_j-a_i$ ，它的系数就是这个差值出现的次数，由于本题要求的都是 $\prod$ 符号，所以我们预处理前面的阶乘和分子，后面的我们枚举全部的大于 $0$ 的幂次，做快速幂就可以实现了，还有要注意的两点，第一是实现的时候 $NTT$ 不能用负数做下标，所以我们要用一个偏移量 $P=1000001$ 去处理一下负数，第二本身由于题目给了 $a_i<a_{i+1}$ 所以对于相同的 $x=a_j-a_i$ 来说最多就是 $n$ 个，不会超过 $5·10^5$ 个，也不用考虑其他的欧拉降幂去求解快速幂。

综上这题的时间复杂度就在 $O(n\log n)$ 时间内愉快的搞定了，挺好的一道LGV引理题和数学题。

int n;
const int P = 1000001;
int a[500005], jc[500005], inv[500005];

namespace math {
    const int MOD = 998244353;
    inline int add(int x, const int y) { return x += y, x >= MOD ? x - MOD : x; }
    inline int sub(int x, const int y) { return x -= y, x < 0 ? x += MOD : x; }
    inline int mul(const int x, const int y) { return 1ll * x * y % MOD; }
    inline int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) res = mul(res, x);
        return res;
    }
}using namespace math;

namespace NTT {
    int limit;
    int pr = 3; // 能用的ntt的素数原根
    vector<int> A, B, rev;
    void init() {
        int ed = P << 1, bit = -1;
        for (limit = 1; limit <= ed; limit <<= 1) ++bit;
        A.resize(limit); B.resize(limit); rev.resize(limit);
        for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    void ntt(vector<int>& P, int op) {
        for (int i = 0; i < limit; ++i) {
            if (i < rev[i])swap(P[i], P[rev[i]]);
        }
        for (int mid = 1; mid < limit; mid <<= 1) {
            int euler = qpow(pr, (MOD - 1) / (mid << 1));
            if (op < 0)    euler = qpow(euler, MOD - 2);
            for (int i = 0, pos = mid << 1; i < limit; i += pos) {
                int wk = 1;
                for (int j = 0; j < mid; ++j, wk = mul(wk, euler)) {
                    int x = P[i + j], y = mul(wk, P[i + j + mid]);
                    P[i + j] = add(x, y), P[i + j + mid] = add(x, MOD - y);
                }
            }
        }
        if (op > 0)    return;
        int inv = qpow(limit, MOD - 2);
        for (int i = 0; i < limit; ++i)    P[i] = mul(P[i], inv);
    }
    void work() {
        for (int i = 1; i <= n; ++i) A[a[i]] = 1;
        for (int i = 1; i <= n; ++i) B[P - a[i]] = 1;
        ntt(A, 1), ntt(B, 1);
        for (int i = 0; i < limit; ++i)    A[i] = mul(A[i], B[i]);
        ntt(A, -1);
    }
};

int solve() {
    n = read();
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        jc[i] = jc[i - 1] * i % MOD;
    }
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; ~i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = mul(mul(ans, (a[i] + 1)), inv[i]);
    }
    NTT::init();
    NTT::work();
    for (int i = P + 1; i <= 2 * P; ++i) {
        ans = mul(ans, qpow(i - P, NTT::A[i]));
    }
    print(ans);

    return 1;
}

2021牛客暑期多校训练营9 C、Cells

C、Cells

题目大意

Solution