#1888. 子集和

    ID: 1888 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>CTT赛事:contest1858来源:qoj.ac数据:公开样例差分前缀和

子集和

子集和

题目描述

标题: 子集和 - Problem - QOJ.ac

#9646. 子集和

Statistics

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