Comet OJ 16 G

令 \(a_0=1\)，对于 \(1\sim n\) 中的每个 \(i\)，在 \([0,i)\) 中随机 \(k\) 个非负整数 \(p_1,p_2...p_k\) 令 \(a_i=\sum a_{p_j}\)

你需要计算 \(a_n^k\) 的数学期望。

\(n\le 10^5,k\le 10\)

Solution

对上述问题做组合转换：问题等价于先确定所有点的连边情况（注意边带标号），然后计算从 \(0\) 处出发的 \(k\) 条带标号流量流至 \(n\) 处的方案数（两种方案不同当且仅当任意一条带标号流流动的方式不同）

于是考虑在钦定一种流法之后计算答案，此时枚举位置 \(i\)，则位置 \(i\) 处的贡献仅关乎其可以连向外部的边数。

不难考虑到对答案的贡献产生变换的部分来自于相同的点流向相同的点的过程，于是我们只需要知道一种 \(k\) 个点的集合划分（同处集合表示两者位于同一个点），然后考虑选定其中的一个子集使其流向 \(i\) 处，来自相同集合的点可能共用相同的边，并在此时计算方案数即可。

初步的暴力实现是 \(\mathcal O(n\cdot \textrm{Bell}(k)\cdot 2^k)\) 的算法，可以优化到不同的复杂度。

不难注意到 \(k\) 个节点是本质相同的，一个集合划分对答案的贡献是无序的（或者说节点允许任意排布均是相同的）

于是我们只需要预处理一种集合划分（拆分数）向另一种集合划分（拆分数）处转移时的方案数即可，附带的，我们需要计算其 \(i-本质不同出边\) 的和。

此时可以做到 \(\mathcal O(n\cdot k\rho(k)^2)\)

事实上，有效的转移并没有达到 \(\rho(k)\) 的级别，我们预处理所有有效的转移即可做到 \(\mathcal O(f(k)\cdot n+S(k))\) 的复杂度。其中 \(f(k)\) 表示有效的转移数，\(S(k)\) 表示预处理的时候暴搜转移数的复杂度代价，可以近似认为是 \(\rho(k)\cdot 3^{\frac{2}{3}k}\cdot k\)（当然这是上界，实际上小得多）

如何更进一步的优化呢？

我们考虑形式化的描述这个问题：

相当于给定了一个大小为 \(\rho(n) \cdot \rho(n)\) 的矩阵 \(A\)，，其内部每个元素是一个多项式，设 \(A(x)\) 表示将矩阵 \(A\) 中的每个多项式代入 \(x\) 这个点值后得到的矩阵，需要计算 \(A(1)\times A(2)\times A(3)\times ... \times A(N)\)

我们朴素实现可以做到 \(\mathcal O(n\cdot \sum \deg(A_{i,j}))\)，利用多点求值+分块可以做到 \(\mathcal O(\rho(n)^2\sqrt{Nk}\log )\)

暂时还没过。。。不知道咋优化了。。。（上面这玩意儿显然不可写）