AGC009E Eternal Average

题意：黑板上有 个 和 个 ，每次可以选择 个数字将其擦除，然后把它们的平均数写上去。

保证 能被 整除。于是，这样一直操作最终只会剩下一个数字，问这个数字有多少种不同的可能。

答案对 取模。

，时限 。

---

神必题。

将操作刻画为 叉树。每次将新产生的节点与擦除的 个节点连边，点权为直接儿子的平均数。

记 个 的深度分别为 （根的深度为 ），则最终的数为 。

将 写作 进制小数 ，其中 。

问题变为：有多少个 进制小数可以生成合法的操作树。

我们知道，假如所有叶子都是 ，则根节点的点权一定是 。

设 个 的深度为 ，则有 。这是一个必要条件。

实际上，这个条件同时也是充分的 ： 将 写成小数，最后一位一定和 的最后一位和为 而产生进位，然后再次必须和为 。

根据这个过程不难构造出对应的树。

• 故问题转化为：

  求符合下列条件的实数 的个数：

  • 可以写成 个 的幂的和。

  • 可以写成 个 的幂的和。

---

对于 进制小数 ，需要满足下列条件：

考虑 。设 表示填写了 个数位，目前的数位和为 ，最后一个数是否为 。（统计答案时钦定末位非 ）

边界为 。

则有如下转移 ：

利用前缀和优化即可 转移。

这里 只会达到 级别， 可以达到 级别。

复杂度为 。