Stirling

为了方便: 简记第一类斯特林数为S_1,第二类斯特林数为S_2

\begin{aligned} {n\brack k}&=(n-1){n-1\brack k}+{n – 1\brack k – 1} \\ \binom nm &= m\binom {n-1}{m}+\binom {n-1}{m-1}\\ \end{aligned}

继续阅读 Stirling

[Zjoi2016]大森林

续命题 (#@*^Y!&

sol

  • 如果同时维护n棵树形态并不可取.
  • 发现所有\text{opt: 2}操作放在加点操作结束后询问答案相同.

故考虑离线维护每棵树的形态, 确切来说, 就是维护当前树与前一棵树的区别.

继续阅读 [Zjoi2016]大森林

Prüfer

Que: 对于n节点的无根树, 共有几种不同的形态 ?

Ans: n^{n-2}

引入Prüfer编码来帮助我们更好的解决问题:

对于一棵树, 进行如下操作:

  1. 寻找当前 度=1 的节点(叶), 在序列中添加其邻节点编号并且删除该点
  2. 重复上述操作, 直到图中剩两个点为止

继续阅读 Prüfer