用于处理形如 形式的式子. 要求 互不相同.

• 算法
• 例题
  • CF923E Perpetual Subtraction

算法#

我们先考虑最简单的形式 . 令 , 其中 是常数.

但是在此之前我们有必要先说明这样的 存在. 可以把所有 都展开后用线性空间的理论来论证, 这里我省略了.

我们发现 . 令 , 由 互不相同得到 .

我们发现有如下推导成立:

.

考察形如 形式的式子, 容易发现最后所得式子是形如 的形式的式子. 但是要注意 必须不大于 , 否则 可能不在 张成的线性空间内.

例题#

CF923E Perpetual Subtraction#

初始时, 黑板上有一个正整数 , 初始为 的概率是 . 每一轮执行以下操作:

• 从 内随机选取一个正整数 .

• 把 擦掉，替换成 .

给定 , 对每个 求 轮之后这个数为 的概率.

.

解法#

考虑初始是 最终是 的概率, 可以写成生成函数的形式:

后面的式子用有理展开处理:

.

令 , 再设 可以一次卷积处理.

由 , 令 , 可以一次卷积处理.