#1890. problem
problem
problem
题目描述
标题: problem - Problem - QOJ.ac
#9649. problem
The problem was used in the following contests:
题目描述
给定 n 个区间 [li,ri] 和一个常数 k。
对两个区间 [l,r] 和 [l′,r′],定义函数 f([l,r],[l′,r′]) 为区间 [l,r] 和 [l′,r′] 的交集长度。
更形式化地,我们有:
f([l,r],[l′,r′])={0if r′<l or l′>rmin(r,r′)−max(l,l′)+1otherwise
给定 m 组询问,每次给出区间 [L,R],你需要求出 ∑i=1nf([L,R],[li,ri])k,对 109+7 取模。
输入格式
第一行包含三个整数 n,k,m。
接下来的 n 行每行包含两个整数 li,ri。
接下来的 m 行每行包含两个整数 L,R。
输出格式
输出 m 行,每行一个整数表示 ∑i=1nf([L,R],[li,ri])k,对 109+7 取模。
样例
样例 1 输入
3 1 2
1 1
1 2
1 3
1 2
1 3
样例 1 输出
5
6
样例 1 解释
对于第一个询问,答案为 f([1,1],[1,2])+f([1,2],[1,2])+f([1,3],[1,2])=1+2+2=5。
对于第二个询问,答案为 f([1,1],[1,3])+f([1,2],[1,3])+f([1,3],[1,3])=1+2+3=6。
样例 2 输入
4 2 4
1 4
2 3
1 3
2 4
1 4
2 3
1 3
2 4
样例 2 输出
38
16
26
26
样例 2 解释
对于第一个询问,答案为 f([1,4],[1,4])2+f([2,3],[1,4])2+f([1,3],[1,4])2+f([2,4],[1,4])2=16+4+9+9=38。
数据范围
对于所有数据,保证:1≤n,m≤105,1≤k≤14,1≤li≤ri≤n,1≤L≤R≤n。
测试点编号 n,m≤ k ri,R≤ 特殊性质 1∼2 2×103 ≤14 n 无 3∼4 105 =1 n 无 5∼10 105 =2 n 无 11∼12 105 ≤8 minn,600 无 13∼20 105 ≤8 n A 21∼23 105 ≤8 n 无 24∼25 105 ≤14 n 无
特殊性质 A:保证所有给出的区间两两之间要么相等,要么不存在包含关系。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1 2
1 1
1 2
1 3
1 2
1 3
5
6
样例 2
4 2 4
1 4
2 3
1 3
2 4
1 4
2 3
1 3
2 4
38
16
26
26