Luogu7445 「EZEC-7」线段树

题意：维护一个长度为 的数组，初始时全为 。

进行 次区间加操作，求最后数组中各个位置的值。

考虑使用线段树维护，每次区间加时打上懒标记（不下推），最后一并下推。

每次区间加操作的区间在 个区间中等概率随机，值在 中随机。

问最后推标记时，推标记的期望次数。（若当前节点的加法标记为 则不会触发推标记，反之则会触发）

答案对 取模，，时限 。

---

• 前置芝士：拉格朗日反演。

首先不难发现，在推标记的过程中，访问到点 时， 的标记是自己以及祖先的初始标记的和。

分别考虑线段树上的每个节点 。

某个区间操作会在 的祖先上打标记，充要条件是操作区间包含 。故概率为 。

枚举影响到该点的操作个数 ，写出该点的期望贡献 ：

其中 是 个 内随机整数和为 的概率。

将上式看作关于 的多项式，整理成 :

先构造出 ，则

这只需进行多点求值。

问题只剩如何求解 。

---

对于 ，显然总方案数是 ，故只需再求出符合要求的方案数。

单个整数的生成函数为 ，则 。

这让人联想到拉格朗日反演中的经典问题，但又略有不同。

令 ，有 ，故 有复合逆。

这需要使用另类拉格朗日反演 ：（普通拉格朗日反演会遇到边界情况）

现在还需求出 。相当于解方程：

不难使用牛顿迭代求解。

复杂度 。