Help Yourself

提交数: 9, 通过率: 0%, 平均分: 0

题目描述:

Bessie 得到了一条一维数轴上的 NN 条线段（1≤N≤105）。第 i 条线段包含满足 li≤x≤ri 的所有实数 x。

定义一组线段的并为所有被至少一条线段所包含的实数 x 的集合。定义一组线段的复杂度为这组线段的并的连通区域数量。

Bessie 想要求出给定的 N 条线段组成的集合的所有 2N 个子集的复杂度之和模 109+7 的值。

通常你的任务是帮助 Bessie。然而这次，你就是 Bessie，没人来帮你。请吧！

测试点性质：
  • 测试点 2-3 满足 N≤16。
  • 测试点 4-7 满足 N≤1000。
  • 测试点 8-12 没有额外限制。

输入格式:

第一行包含 N。

以下 N 行每行包含两个整数 li 和 ri。保证 li<ri，且所有 li,ri 均为 1…2N 中的不同整数。

输出格式:

输出答案模 109+7 的值。

样例输入:

3
1 6
2 3
4 5

样例输出:

8

提示:

所有非空子集的复杂度如下。

{[1,6]}⟹1,{[2,3]}⟹1,{[4,5]}⟹1
{[1,6],[2,3]}⟹1,{[1,6],[4,5]}⟹1,{[2,3],[4,5]}⟹2
{[1,6],[2,3],[4,5]}⟹1

答案为 1+1+1+1+1+2+1=8。

时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 FEB Gold