【省選模拟】Fac （生成函數）（組合意義）（拉格朗日反演）（倍增）（多項式全家桶）

• 沒有題解是真的秀，連蒙帶猜搞了一天結果今天早上才寫完，不過還好有 3 個神仙學長助力

  不知道題解是怎麼想到的，是以隻好直接說結論了

• 經觀察發現可以先求出，這個在 的時候是卡特蘭數也就是二叉樹的個數

  考慮将其擴充為 叉樹，即證 是

• 證明：

  中間用到了拉格朗日反演

  後面的一個是 ，是以組合意義是 ，令 ，即可得方案數為

  也同時證明了 個點的 叉樹（有根無标号兒子有順序）的個數是

• 于是問題就變成了解

  這個是可以倍增的，假設已經求得

  考慮擴充到

  我們隻需要求出 的系數，不妨令為 ，我們用 表示新的

  考慮前一半的貢獻， 在 是有貢獻的，不妨令為

  而 對 的貢獻隻會有一個 選到 ，故可以列出方程

  解出即可，倍增算貢獻還是比較巧妙

  ​​，最慢的點跑了