比赛场次 465
比赛名称 USACO铂金组&NOIonline模拟赛
比赛状态 已结束比赛成绩
开始时间 2020-03-03 08:30:00
结束时间 2020-03-03 12:00:00
开放分组 全部用户
注释介绍
题目名称 Help Yourself(Platinum)
输入输出 usaco_Feb_helps.in/out
时间限制 2000 ms (2 s)
内存限制 256 MiB
测试点数 16 简单对比
用户 结果 时间 内存 得分

Help Yourself(Platinum)

★★★★   输入文件:usaco_Feb_helps.in   输出文件:usaco_Feb_helps.out   简单对比
时间限制:2 s   内存限制:256 MiB

【题目描述】

Bessie 得到了一条一维数轴上的 $N$ 条线段($1\le N\le 10^5$)。第 $i$ 条线段包含满足 $l_i\le x\le r_i$ 的所有实数 $x$。

定义一组线段的为所有被至少一条线段所包含的实数 $x$ 的集合。定义一组线段的复杂度为这组线段的并的连通区域数量的 $K$ 次方($2\le K\le 10$)。

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

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

【输入格式】

第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。保证 $l_i< r_i$,且所有 $l_i,r_i$ 均为 $1 \ldots 2N$ 中的不同整数。

【输出格式】

输出答案模 $10^9+7$ 的值。

【样例输入】

3 2
1 6
2 3
4 5

【样例输出】

10

【样例解释】

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

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

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

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

答案为 $1+1+1+1+1+4+1=10$。

【提示】

对于$ 13\% $的测试数据(测试点$ 1 \sim 2 $),满足$ N\le 16 $。 

另有$ 19\% $的测试数据(测试点$ 3 \sim 5 $),满足$ N\le 10^3 , K = 2 $。

对于$ 50\% $的测试数据(测试点$ 1 \sim 8 $),满足$ N\le 10^3 $。

另有$ 50\% $的测试数据(测试点$ 9 \sim 16 $),测试点 $T$ 满足 $K = 3 + ( T - 9 ) $。

对于$ 100\% $的测试数据,均满足上文所给出的数据规模。

【来源】

USACO 二月公开赛 Platinum 组