為什么會有人推得出來第三題想不出來簽到題啊 (⊙_⊙)？

題面

有一棵有根樹 \(T\)。從根節點出發，在點 \(u\) 時，設點 \(u\) 還有 \(d\) 個未訪問過的兒子，則有 \(\frac1{d+1}\) 的概率向上（深度較小的方向）走一步，有 \(\frac1{d+1}\) 的概率走向一個未訪問過的兒子。從根節點往上走則結束游走。

記 \(f(T)\) 為這樣游走到達的點的深度之和的期望。

給定 \(N\)（\(N\le10^7\)），對 \((1,2,\dots,N)\) 的所有排列 \(P\)，建立小根的笛卡爾樹 \(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\)。

先不管 \(g_n\)，繼續推導 \(f_n\) 的式子：

這么多階乘容易讓人聯想到指數生成函數的樣子，不妨化一下：

顯然可以把 \(\frac{f_n}{n!}\) 看成一個整體，發現轉移式的主體是一個前綴和。記 \(F_n\) 為 \(\frac {f_i}{i!}\) （\(i\ge1\)）的前綴和，則式子可以簡化為：

\(F_0=0\)，多次迭代過后可以得到 \(F_n\) 的通項。

有一個類似于調和級數前 \((n+1)\) 項的東西，設調和級數前 \(n\) 項為 \(H_n\)。

現在回頭看一看 \(g_n\)，大致轉移與 \(f_n\) 相同，但是根的貢獻是 \(f_n\)，也即 \(siz_n\) 的期望值（所以先推導 \(f\)）。

同樣的，我們記 \(G_n\) 為 \(\frac{g_i}{i!}\) 的前綴和，把 \((1)\) 代入。

對 \((2)\) 進行迭代也可以得到 \(G_n\) 的通項公式：

我們要算的答案是 \(g_n=n!(G_n-G_{n-1})\)，由于 \(mod\) 不一定是質數，那還得繼續推式子。

這樣分母就可以全部抵消了，預處理調和級數前 \(n\) 項系數的前綴和與后綴和可以 \(\mathcal O(n)\) 求解。

源代碼

/* Lucky_Glass */
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e7 + 10;
typedef long long llong;

int mod;

inline int reduce(llong key) {
  return int((key %= mod) < 0 ? key + mod : key);
}

int pre[N], suf[N];

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

  int n; scanf("%d%d", &n, &mod);

  pre[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);

  int 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 = reduce(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);
  return 0;
}

THE END

Thanks for reading!