7/13 D 题题解
x义x
·
·
个人记录
题目大意
插 n 个长度为 l，每一位都在 1,2,...,c 中间随机的串到一个 trie 里，求 trie（除了根）的期望节点数。对于 n=1,2,...,N 都要输出答案。
题解
考虑每一个串的期望贡献。设其他串和它的 lca 长度为 i。答案为
\sum_{i=0}^l(l-i)P(lca=i)
l+1-\sum_{i=0}^lP(lca\ge i)
考虑 P(lca<i)。一个串与当前串的 lca\ge i 的概率显然是 c^{-i}，所以 n-1 个就是 1-(1-c^{-i})^{n-1}。（n=1 的时候有一点问题，要特判）
所以答案为
-[n=1]+\sum_{i=0}^l(1-c^{-i})^{n-1}
-[n=1]+\sum_{i=0}^l\sum_{j=0}^{n-1}{n-1\choose j}(-c^{-i})^j
-[n=1]+\sum_{j=0}^{n-1}{n-1\choose j}(-1)^j\sum_{i=0}^l c^{-ij}
如果 c=1 那么特判，否则
-[n=1]+l+1+\sum_{j=1}^{n-1}{n-1\choose j}(-1)^j\dfrac{1-c^{-j(l+1)}}{1-c^{-j}}
明显就是卷积形式了，卷就好了。