「雅礼集训2017」PATH

2019 年 07 月 20 日

给定长度为 $n$ 的序列 $\{a_i\}$ ，满足 $a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0$ ，求出在 $n$ 维空间中从点 $(0, 0, \ldots, 0)$ 随机游走到点 $(a_0, a_1, \ldots, a_{n - 1})$ ，满足经过的所有点 $(x_0, x_1, \ldots, x_{n - 1})$ 都有 $x_0 \geq x_1 \geq \cdots \geq x_{n - 1}$ 的概率，随机方式是每一步均匀随机一个 $i\in [1,n]\cup \mathbb N_+$ 并令 $x_i:=x_i+1$ 。

$1\le n, a_i \leq 5\times 10^5$ 。答案对 $1004535809$ 取模。

题解

利用钩子定理相关知识我们可以直接得到

ans = \frac { \displaystyle \frac {m!} { \prod\limits_{(i, j) \in \lambda} h(i, j)}} { \displaystyle \frac {m!} {\prod\limits_{i=1}^n a_i} }

其中 $m = \sum\limits_{i=1}^n a_i$ ， $\lambda$ 是第 $i$ 行长度为 $a_i$ 的杨表， $h_\lambda(i, j)$ 表示杨表 $\lambda$ 中第 $i$ 行第 $j$ 个元素的钩子长度。

根据

\prod\limits_{(i, j) \in \lambda} h_\lambda(i, j) = \frac { \prod\limits_{i=1}^n (a_i + n - i)! } { \prod\limits_{1 \leq i < j \leq n} \left((a_i - i) - (a_j - j)\right)}

那么

\begin{aligned} ans &= \frac { \displaystyle \frac {m! \prod\limits_{1 \leq i < j \leq n} \left((a_i - i) - (a_j - j)\right)} { \prod\limits_{i=1}^n (a_i + n - i)! }} { \displaystyle \frac {m!} {\prod\limits_{i=1}^n a_i} } \\ &= \frac { \prod\limits_{i=1}^n a_i} { \prod\limits_{i=1}^n (a_i + n - i)! } \times \prod\limits_{1 \leq i < j \leq n} \left((a_i - i) - (a_j - j)\right) \end{aligned}

发现处理的瓶颈在于右半部分。

注意到 $\{a_i\}_{i=1}^n$ 为仅为 $O(n)$ 级别。并且由于 $\forall i < j ,\; a_i \geq a_j$ ，可得 $\forall i < j, (a_i - i) > (a_j - j)$ 。考虑卷积优化。

可以开两个多项式，一个幂次为 $(a_i - i)$ 一个幂次为 $-(a_i - i)$ ，卷积一波只取幂次为整数的即可。（如果由 $i \geq j$ 的贡献而成，一定满足幂次 $\leq 0$ ）。

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

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e6 + 10, mod = 1004535809;
int n, l, tmp_n, tmp_m, ans = 1;
int a[N], f[N], g[N], h[N], w[N], rev[N], fac[N], ifac[N];
void setup(int *a, int &l, int n) { ++a[n], l = std::max(l, n); }
inline int dec(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
inline int inc(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
inline int mul(int a, int b) { return (ll)a * b - (ll)a * b / mod * mod; }
inline int inv(int x) { return x < 2 ? 1 : mul(mod - mod / x, inv(mod % x)); }
inline int fpow(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) s = mul(s, a);
  return s;
}
void init_fac(int n) {
  fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= n; i++) fac[i] = mul(fac[i - 1], i);
  for (int i = 2; i <= n; i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
  for (int i = 2; i <= n; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
}
void ntt(int *a, int l) {
  for (int i = 0; i < l; i++)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (int len = 1; len < l; len <<= 1)
    for (int i = 0; i < l; i += (len << 1))
      for (int j = 0; j < len; j++) {
        int x = a[i + j], y = mul(a[i + j + len], w[j + len]);
        a[i + j] = inc(x, y), a[i + j + len] = dec(x, y);
      }
}
void mul(int *a, int *b, int *c, int n, int m, int &l) {
  l = 1;
  int k = 0;
  while (l < n + m - 1) l <<= 1, ++k;
  for (int i = 0; i < l; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  for (int wn, len = 1; len < l; len <<= 1) {
    wn = fpow(3, (mod - 1) / (len << 1)), w[len] = 1;
    for (int i = 1; i < len; i++) w[i + len] = mul(w[i + len - 1], wn);
  }
  int inv_l = inv(l);
  ntt(a, l), ntt(b, l);
  for (int i = 0; i < l; i++) c[i] = mul(a[i], b[i]);
  std::reverse(c + 1, c + l), ntt(c, l);
  for (int i = 0; i < l; i++) c[i] = mul(c[i], inv_l);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  init_fac(n + a[1]);
  for (int i = 1; i <= n; i++) {
    ans = mul(ans, mul(fac[a[i]], ifac[a[i] + n - i]));
    setup(f, tmp_n, a[i] - i + n);
    setup(g, tmp_m, -a[i] + i + a[1]);
  }
  mul(f, g, h, tmp_n + 1, tmp_m + 1, l);
  for (int i = 1, d = n + a[1]; i + d < l; i++) {
    ans = mul(ans, fpow(i, h[i + d]));
  }
  cout << ans << endl;
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论