Luogu6144 [USACO20FEB] Help Yourself P

题意：给出 个区间 ，选择这些区间的一个子集 （有 种方案） ，记 为 中的区间取并后形成的连通块数目。求所有 的 的 次方和。

答案对 取模，，，时限 。

---

以左端点排序，逐次加入线段，使用数据结构维护 DP。

设 为最右端点为 的所有方案的连通块数目的 次方和。

加入一条线段 的贡献是：

• 为最右端点

  可能 和旧的集合无交集，此时新增一个联通快。

  将 加到 处。需要二项式展开，一次复杂度是 的。

  可能和旧的集合有交集，此时直接将 的和加入 即可。

• 不是最右端点

  由于左端点递增，新的区间一定会被旧的区间包含。

  将 乘以 即可。

直接线段树维护。需要分别记录 次幂，复杂度。