DDOSvoid's Blog

2021牛客多校9 C Cells

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11260/C

简要题意：有一张网格图，现在有 $n$ 个棋子分别要从 $(0,a_i)$ 走到 $(i,0)$，棋子只能向下或者向右走，问有多少种方案，使得每个棋子都能从起点走到终点，且对于所有棋子，走过的路径互不相交，方案数对 $998244353$ 取模

$n\le 5\times 10^5$

Solution

我们考虑 $LGV$​ 引理，构造矩阵 $A_{i,j}=\binom{a_i+j}{j}=\frac{(a_i+j)!}{a_i!j!}$，由于矩阵的大小是 $n\times n$​ 的，所以我们不能高消，考虑如何化简矩阵使得可以通过别的方式求出行列式

首先我们把每列的 $j!$ 个提出来，然后注意到 $A_{i,j}=\frac{(a_i+j)!}{a_i!}=\prod_{k=1}^ja_i+k$，这个东西我就可以用第 $j$ 列去消第 $j+1$ 列，得到 $A_{i,j}=(a_i+1)^j$，这显然是一个范德蒙德矩阵，其行列式就是 $(\prod_{i=1}^na_i+1)\prod_{1\le j<i\le n}(a_i+1-(a_j+1))$ 后者可以用卷积来算

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define maxn 1000010
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

typedef std::vector<int> Poly;
namespace Pol {
    inline int add(int a, int b) { return (a += b) >= p ? a -= p : a; }
    inline int sub(int a, int b) { return (a -= b) < 0 ? a += p : a; }
    inline void inc(int &a, int b) { (a += b) >= p ? a -= p : a; }
    inline void dec(int &a, int b) { (a -= b) < 0 ? a += p : a; }

    const int N = 4200000;
    int a[N], b[N];

    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }

    void NTT(int *a, int n, int type) {
        static int w[N]; ll G = 3, Gi = pow_mod(G, p - 2); 
        for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
        for (int i = 2, m = 1; i <= n; m = i, i *= 2) {
            ll wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i);
            w[0] = 1; for (int j = 1; j < m; ++j) w[j] = wn * w[j - 1] % p;
            for (int j = 0; j < n; j += i) 
                for (int k = 0; k < m; ++k) {
                    ll t1 = a[j + k], t2 = 1ll * a[j + k + m] * w[k] % p; 
                    a[j + k] = add(t1, t2);
                    a[j + k + m] = add(t1, p - t2);
                }
        }
        if (type < 0) {
            ll inv = pow_mod(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = inv * a[i] % p; 
        }
    }

    Poly Mul(const Poly &A, const Poly &B, int n1, int n2) {
        int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        copy_n(A.begin(), n1, a), fill(a + n1, a + n, 0);
        copy_n(B.begin(), n2, b), fill(b + n2, b + n, 0);
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % p; 
        NTT(a, n, -1); Poly ans(n1 + n2 - 1); copy_n(a, n1 + n2 - 1, ans.begin());
        return ans;
    }
    
}  // namespace Pol

ll fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
}

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 

    cin >> n; int N = 1000000; Poly A(N + 1), B(N + 1); ll ans = 1; 
    for (int i = 1, x; i <= n; ++i) cin >> x, A[x] = B[-x + N] = 1, ans = ans * (x + 1) % p;
    Poly res = Pol::Mul(A, B, N + 1, N + 1); init_C(n);
    for (int i = N + 1; i <= 2 * N; ++i) ans = ans * pow_mod(i - N, res[i]) % p;
    for (int i = 1; i <= n; ++i) ans = ans * inv[i] % p;
    cout << (ans + p) % p << "\n";
    return 0;
}