#1888. 子集和
子集和
子集和
题目描述
标题: 子集和 - Problem - QOJ.ac
#9646. 子集和
The problem was used in the following contests:
题目描述
有 n 个物品,物品 i 有两个属性 ai,bi。对于一个物品集合 S,定义 f(S) 是如下问题的答案:
- 对于每个物品 i∈S,选择 0,ai,bi 三个数中的一个,使得所有物品选择的数之和是 m 的倍数的方案数。
定义物品集合 S={1,2,…,n}。有 q 次询问,每次给定四个正整数 1≤l1≤r1<l2≤r2≤n,求:
∑l1≤i≤r1∑l2≤j≤r2f(S∖{i,j})
答案对 109+7 取模。
输入格式
第一行,三个正整数 n,m,q。
接下来 n 行,每行两个非负整数 ai,bi。
接下来 q 行,每行四个正整数 l1,r1,l2,r2,表示一次询问。
输出格式
q 行,每行一个非负整数,表示答案对 109+7 取模后的值。
样例
输入
6 10 5
2 3
7 1
1 4
8 1
2 5
8 9
1 2 3 4
1 1 2 2
1 1 5 5
1 3 4 6
1 5 6 6
输出
33
9
11
80
37
数据范围
对于所有数据:
- 1≤n≤104
- 2≤m≤200
- 1≤q≤106
- 0≤ai,bi<m (1≤i≤n)
子任务 n≤ m≤ 特殊性质 分值 1 100 — AB 5 2 500 — AB 5 3 — 20 AB 20 4 — 150 A 15 5 — — B 15 6 — — C 10 7 — — l1=r1,l2=r2 5 8 — — — 25
特殊性质 A:每次询问都在所有满足条件的 (l1,r1,l2,r2) 中随机选择。
特殊性质 B:q≤105。
特殊性质 C:对于每个物品 i,ai=bi。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6 10 5
2 3
7 1
1 4
8 1
2 5
8 9
1 2 3 4
1 1 2 2
1 1 5 5
1 3 4 6
1 5 6 6
33
9
11
80
37