当前位置：职场发展 > 《SOL》清理笛卡尔（模拟竞赛）

《SOL》清理笛卡尔（模拟竞赛）

发布：2023-10-06 05:07

为什么有人能推导出第三题却不能推导出签到题(⊙_⊙)？

标题

有一棵树，有根\(T\)。从根节点开始，在点\(u\)处，设置点\(u\)，并且有\(d\)没有被访问过如果的儿子的概率走向未访问过的儿子。从根节点向上走结束步行。

注\(f(T)\)是这样一次行走所到达的点的深度总和的期望。

给定 \(N\)(\(N\le10^7\))，对于 \((1,2,\dots,N) 对于\)\(P\)的所有排列，构建一个具有小根\(T_P\)的笛卡尔树，并找到

\[\sum_{P}f(T_p) \]

答案是给定正整数的模 \(mod\) (\(n\lt mod\le2\times10^9\)), \ ( mod\) 不一定是素数。

分析

首先分析\(T\)上的行走方法。笛卡尔树是二叉树。如果当前点有一个未访问过的儿子，则：

只有一个儿子时，他有 \(\frac 12\) 的概率会去找那个儿子；
有两个儿子的时候，有\(\frac 13\)第一次去找儿子的概率是\(\frac 13\times\frac 12\) ) 第二次去儿子那里的概率，即总共有 \(\frac 12\) 去儿子那里的概率。

所以我们发现，不管儿子有多少个，得到儿子的概率总是\(\frac12\)，这会让我们后续的推导变得容易很多。

考虑到笛卡尔树本身是一种分而治之的结构——将最小值分为两个区间分别构建笛卡尔树，而对于一个排列来说建立笛卡尔树只与元素个数有关在安排中。由此，您可以设计一个以排列元素的大小作为状态的DP。

设 \(g_n\) 表示“\(n\) 元素\(P_n\)”的所有排列构建笛卡尔树 \(T_{P_n}\)，\(f(T_{P_n})\)"、\(g_N\)之和就是我们所需要的回答。然而，深度之和并不容易直接计算（虽然可以使用期望的线性度将其拆分为单点贡献，但后续的推导会绕一个大圈，这不像下面的方法那么直观）。

有一个非常常用的属性：\(\sum dep=\sum siz\)，所以设计辅助DP\(f_n\)的意思是“对于” \ (n\) 元素的所有排列 \(P_n\) 构建笛卡尔树 \(T_{P_n}\)，起始预计达到多少个从根点开始”。

传输考虑枚举左子树\(l\)的大小，并选择左子树\(\binom{n-1}{l}\)的元素。利用期望的线性度，左子树的贡献是 \(f_l\) 乘以右子树的选项数量。一种排列显然对应于笛卡尔树，因此贡献为 \(f_l\times(n-l-1)\)。右子树也是如此，最后还要加上根的贡献。对于\(n!\)，笛卡尔树根的贡献为\(1\)。

\[f_n=n!+\frac 12\sum_{l=0}^{n-1}\binom{n-1}{l}\Big((n-l-1)!f_l+l!f_ {n-l-1}\大) \]

忽略\(g_n\)，继续推导\(f_n\)的公式：

\[\开始{对齐} f_n&=n!+\sum_{l=0}^{n-1}\binom{n-1}{l}(n-l-1)!f_l\\&=n!+\sum_{l=0}^{n-1}(n-1)!\frac{f_l}{l!} \结束{对齐} \]

这么多阶乘很容易让人想起指数生成函数，不妨改成：

\[\frac{f_n}{n!}=1+\frac 1n\sum_{l=0}^{n-1}\frac{f_l}{l!} \]

显然我们可以将\(\frac{f_n}{n!}\)视为一个整体，发现转账的主体是一个前缀和。令 \(F_n\) 为 \(\frac {f_i}{i!}\) (\(i\ge1\) 的前缀和) ，那么公式可以简化为：

\[F_n-F_{n-1}=1+\frac 1nF_{n-1}\到 F_n=1+\frac{n+1}{n}F_{n-1} \]

\(F_0=0\)，经过多次迭代，可得到\(F_n\)的通项。

\[F_n=\sum_{i=2}^{n+1}\frac{n+1}{i} \]

在调和级数之前有一个类似于术语\((n+1)\)的内容。设调和级数之前的项\(n\)为\(H_n\)。

\[\开始{对齐} F_n=(n+1)(H_n-1)&\tag{1} \结束{对齐} \]

现在回头看\(g_n\)，近似传递与\(f_n\)相同，但根的贡献是\( f_n\)，即\(siz_n\)的期望值（所以首先推导\(f\)）。

\[\开始{对齐} g_n&=f_n+\frac12\sum_{l=0}^{n-1}\binom{n-1}{l}\Big((n-l-1)!g_l+l!g_{n-l-1}\Big) \\ &=f_n+\sum_{l=0}^{n-1}\binom{n-1}{l}(n-l-1)!g_{l}\\&=f_n+\sum_{l=0}^{n-1}(n-1)!\frac{g_l}{l!}\\ &=n!+\sum_{l=0}^{n-1}(n-1)!\frac{g_l+f_l}{l!} \结束{对齐} \]

同样，我们记住\(G_n\)作为\(\frac{g_i}{i!}\)的前缀和，并把\( (1)\) 替代。

\[\开始{对齐} G_n-G_{n-1}&=1+\frac 1n(F_{n-1}+G_{n-1})\notag\\ &=H_n+\frac 1nG_{n-1}&\notag\\ \到G_n&=H_n+\frac{n+1}{n}G_{n-1}&\tag{2} \结束{对齐} \]

迭代\((2)\)还可得到\(G_n\)的通式：

\[G_n=\sum_{i=1}^{n}\frac{n+1}{i+1}H_i \]

我们要计算的答案是\(g_n=n!(G_n-G_{n-1})\)，因为\(mod\)不一定是一个素数，那么我们还要继续推公式。

\[\开始{对齐} g_n&=n!\Big(H_n+\sum_{i=1}^{n-1}\frac{H_i}{i+1}\Big)\\ &=n!H_n+n!\sum_{i=2}^{n}\frac{1}{i}\sum_{j=1}^{i-1}\frac{1}{j}\\ &=n!H_n+\sum_{1\le i\lt j\le n}\frac{n!}{ij} \结束{对齐} \]

这样分母就可以全部抵消了。在对调和级数进行预处理之前，\(n\)的系数的前缀和和后缀和可以通过 \(\mathcal O(n)\) 来求解。

源码

/* Lucky_Glass */
#包括
#包括
#包括常量 int N = 1e7 + 10;
typedef 长长长；

整数模；

内联 int reduce(长键) {
  return int((key %= mod) < 0 ? key + mod : key);
}

int pre[N], suf[N];

int main() {
  freopen("笛卡尔.in", "r", stdin);
  freopen("cartesian.out", "w", stdout);

  整数 n; scanf("%d%d", &n, &mod);

  前[0] = 1;
  for (int i = 1; i <= n; ++i) pre[i] = reduce(1ll * pre[i - 1] * i);
  suf[n + 1] = 1;
  for (int i = n; i; --i) suf[i] = reduce(1ll * suf[i + 1] * i);

  整数 ans = 0;
  for (int i = 1; i <= n; ++i)
    ans = reduce(ans + 1ll * pre[i - 1] * suf[i + 1]);

  int ex_ans = 0;
  for (int i = 2, tmp = 0; i <= n; ++i) {
    tmp =减少(pre[i - 2] + (i - 1ll) * tmp);
    ex_ans = reduce(ex_ans + 1ll * tmp * suf[i + 1]);
  }

  ans = reduce(1ll * ans + ex_ans);
  printf("%d\n", ans);
  返回0；
}