---

题目大意

在 $n$ 维空间中，从原点 $(0,0,\dots,0)$ 走到点 $(a_0, a_1, \dots, a_{n-1})$，其中 $a_0 \ge a_1 \ge \dots \ge a_{n-1} \ge 0$。

每一步只能选择一维坐标增加 $1$。

在所有可能的路径中，随机选择一条路径。求这条路径满足 路径上所有点 $(x_0, x_1, \dots, x_{n-1})$ 都保持 $x_0 \ge x_1 \ge \dots \ge x_{n-1}$ 的概率，对 $1004535809$ 取模。

---

问题转化

设总步数 $S = a_0 + a_1 + \dots + a_{n-1}$。

从原点到终点的总路径数（不考虑路径中点的坐标大小关系限制）是一个经典的多重集排列问题：

$$\text{总路径数} = \frac{S!}{a_0! a_1! \dots a_{n-1}!}$$

因为每一步选择增加哪一维，相当于把 $S$ 步分配给 $n$ 个维度，第 $i$ 维分配 $a_i$ 步。

---

合法路径数

我们要求路径上每时每刻都满足 $x_0 \ge x_1 \ge \dots \ge x_{n-1}$。

这是一个 Gessel–Viennot–Lindström 引理的经典应用场景。

考虑 $n$ 条路径：

• 路径 $i$ 从 $(-i, 0)$ 走到 $(a_{n-i} - i, S)$（在二维网格图上理解），但这里我们直接套用引理。

GVL引理（行列式形式）： 对于起点集合 $A = (A_1, \dots, A_n)$，终点集合 $B = (B_1, \dots, B_n)$，在DAG上从 $A_i$ 到 $B_j$ 的路径数记为 $e(A_i, B_j)$，则从 $A_i$ 到 $B_{\sigma(i)}$ 的不相交路径组数等于 $\det\big(e(A_i, B_j)\big)_{1\le i,j\le n}$。

在我们的问题中，坐标是单调非增的，可以映射为：

• 起点 $A_i = (0, i-1)$
• 终点 $B_j = (a_{j-1}, j-1)$ 在二维格点图上，只能向右或向上走，并且路径不能相交（因为路径相交意味着在某一步 $x_i < x_{i+1}$，破坏了非增条件）。

经过坐标平移，这个问题等价于：从 $(0,i)$ 到 $(a_{n-1-j} + n - 1 - j, n-1)$ 的路径数。

实际上，更简单的理解是：

设 $b_i = a_i + n - 1 - i$，则 $b_0 > b_1 > \dots > b_{n-1} \ge 0$。

那么合法路径数等于：

$$N_{\text{valid}} = \frac{\det\big[ \binom{b_j}{n-1-i} \big]_{0\le i,j\le n-1}}{\prod_{0\le i<j\le n-1} (b_i - b_j)} \times \text{?} $$

但更直接的结论是：

合法路径数 = 矩阵行列式：

$$N_{\text{valid}} = \det\left[ \binom{a_{n-1-j} + n-1-j}{n-1-i} \right]_{0\le i,j\le n-1} $$

---

最终概率

概率 = 合法路径数 / 总路径数

即：

$$P = \frac{ \det\left[ \binom{a_{n-1-j} + n-1-j}{n-1-i} \right]_{0\le i,j\le n-1} }{ \frac{S!}{a_0! a_1! \dots a_{n-1}!} } $$

其中 $S = \sum_{i=0}^{n-1} a_i$。

---

算法实现

1. 读入 $n$ 和 $a$ 数组。
2. 构造 $n \times n$ 矩阵 $M$，其中 $M_{i,j} = \binom{a_{n-1-j} + n-1-j}{n-1-i}$。
3. 计算该矩阵的行列式 $\det(M)$（模 $1004535809$）。
4. 计算总路径数 $T = \frac{S!}{a_0! a_1! \dots a_{n-1}!}$。
5. 输出 $\det(M) \times T^{-1} \bmod 1004535809$。

---

模数处理

模数 $1004535809$ 是质数，可用费马小定理求逆元。

组合数预处理阶乘和逆元阶乘到 $\max(a_i) + n$。

行列式计算使用高斯消元（模意义下），复杂度 $O(n^3)$。

---

参考代码（C++ 框架）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1004535809;
const int N = 500000 + 10; // 根据数据范围调整

int n;
int a[N];
int fac[N], invfac[N];

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i-1] * i % MOD;
    invfac[n] = qpow(fac[n], MOD-2);
    for (int i = n-1; i >= 0; i--) invfac[i] = 1LL * invfac[i+1] * (i+1) % MOD;
}

int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return 1LL * fac[n] * invfac[k] % MOD * invfac[n-k] % MOD;
}

int det(vector<vector<int>> M) {
    int n = M.size();
    int res = 1;
    for (int i = 0; i < n; i++) {
        int pivot = -1;
        for (int j = i; j < n; j++) {
            if (M[j][i] != 0) {
                pivot = j;
                break;
            }
        }
        if (pivot == -1) return 0;
        if (pivot != i) {
            swap(M[i], M[pivot]);
            res = (MOD - res) % MOD;
        }
        res = 1LL * res * M[i][i] % MOD;
        int inv = qpow(M[i][i], MOD-2);
        for (int j = i+1; j < n; j++) {
            int coef = 1LL * M[j][i] * inv % MOD;
            for (int k = i; k < n; k++) {
                M[j][k] = (M[j][k] - 1LL * coef * M[i][k]) % MOD;
                if (M[j][k] < 0) M[j][k] += MOD;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    int max_val = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        max_val = max(max_val, a[i] + n);
    }
    init(max_val);

    vector<vector<int>> M(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            M[i][j] = C(a[n-1-j] + n-1-j, n-1-i);
        }
    }

    int numerator = det(M);

    int denominator = 1;
    int sum_a = 0;
    for (int i = 0; i < n; i++) {
        denominator = 1LL * denominator * invfac[a[i]] % MOD;
        sum_a += a[i];
    }
    denominator = 1LL * denominator * fac[sum_a] % MOD;

    int ans = 1LL * numerator * qpow(denominator, MOD-2) % MOD;
    printf("%d\n", ans);

    return 0;
}

---

总结

本题的关键是将路径单调非增的条件转化为不相交路径问题，然后应用 GVL 引理 得到行列式表达式，最后用线性代数计算行列式并求概率。