Luogu6633 [ZJOI2020] 抽卡

题意：给出一个整数集 。

每次抽奖可以随机获得 中的某个元素，多次抽奖可能重复获得同一个元素。

如果抽出值紧邻的连续 个数，则停止抽奖，问期望轮数。

答案对 取模，，时限 。

---

将已有的卡牌集合看作状态。称已有 个连续数的状态为好的，反之为坏的。

卡牌只会变多，转移显然是个 DAG。

一些经典的期望步数问题中，转移往往是链状的，易于分析。

对于本题而言，转移是具有多个终点（好节点）的 DAG。

由期望的线性性，我们分别求出到达每个点的概率以及在这个点停留的期望时间，相乘求和即为答案。

设 ，不考虑终止。

已有 张卡片的状态共有 种，由对称性，到其中一个状态的概率为 。

而已有 张卡片的状态停留的期望时间显然为 。

考虑终止节点之后，相当于裁掉了一部分 DAG。

注意，好节点的所有后继都是好的，裁去若干全序集对余下部分的到达概率不会有影响。

---

接下来的任务就是：对每个 ，求出坏节点的个数。

显然，值域不连续的两部分之间无影响，卡片个数简单相加，对应加法卷积。

将每个连续段分开求解，最后分治 卷积即可。

一段长度为 的 串，连续的 不达到 个， 的个数总共 个，求方案数。

设一段 的 OGF 为 。

显然，由 个 来分隔这些 的连续段，共分成 段。

方案数为 ，可以补齐成 。

问题转化为求解 的 次幂的 次项系数。这是「幂的横截」，先求出 的复合逆，然后可以用多项式快速幂（配合拉格朗日反演） 计算。

设 的复合逆为 ，则有 牛顿迭代即可做到 。