BZPRO

#5576. [Usaco2020 Feb]Help Yourself

内存限制：512 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

Bessie得到了一条一维数轴上的N条线段（1≤N≤10^5）。
第i条线段包含满足li≤x≤ri的所有实数x。
定义一组线段的并为所有被至少一条线段所包含的实数x的集合。
定义一组线段的复杂度为这组线段的并的连通区域数量的KK次方（2≤K≤10）。
Bessie想要求出给定的N条线段组成的集合的所有2N个子集的复杂度之和模10^9+7的值。
通常你的任务是帮助Bessie。然而这次，你就是Bessie，没人来帮你。请吧！

输入格式

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

输出格式

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

样例

样例输入


			
3 2

1 6

2 3

4 5

样例输出


			
10

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

{[1,6]}==>1,{[2,3]}==>1,{[4,5]}==>1

{[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]}==>1,{[1,6],[4,5]}==>1,{[2,3],[4,5]}==>4

{[1,6],[2,3],[4,5]}==>1

{[1,6],[2,3],[4,5]}==>1

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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository