【清华集训2014】简单回路 - 题目

在一个有障碍点的 $n$ 行 $m$ 列的网格图中，我们用 $(x, y)$ 来表示第 $x$ 行第 $y$ 列的格子。如果该网格图中的回路满足下面两个条件：

则我们称该回路为合法的简单回路。

现在有 $Q$ 个询问，每次询问有多少条合法的简单回路经过了 $(x, y)$ 与 $(x + 1, y)$ 之间的边。

第一行输入三个非负整数 $n$ , $m$ , $k$ ，表示 $n$ 行 $m$ 列的网格图中有 $k$ 个障碍点。

接下来 $k$ 行，每行两个正整数 $x, y$ $(1 \leq x \leq n, 1 \leq y \leq m)$ ，表示 $(x, y)$ 为一个障碍点（可能重复）

接下来一个整数 $Q$ ，表示 $Q$ 个询问。

接下来 $Q$ 行，每行两个正整数 $x, y$ $(1 \leq x \leq n - 1, 1 \leq y \leq m)$ ，询问有多少条合法的简单回路经过了格子 $(x, y)$ 与 $(x + 1, y)$ 之间的边。

输出 $Q$ 行，每行对应一组询问。请将答案 $mod (1000000000 + 7)$ 之后输出。

测试点编号	$n$	$m$	$k$	$q$
1	$100$	$1$	$\leq 100$	$\leq 100$
2	$1000$	$2$	$\leq 100$	$\leq 100$
3	$1000$	$2$	$\leq 100$	$\leq 100$
4	$1000$	$3$	$\leq 100$	$\leq 100$
5	$1000$	$5$	$\leq 100$	$\leq 100$
6	$1000$	$6$	$\leq 100$	$\leq 100$
7	$1000$	$6$	$\leq 100$	$\leq 10000$
8	$1000$	$6$	$\leq 100$	$\leq 10000$
9	$1000$	$6$	$\leq 100$	$\leq 10000$
10	$1000$	$6$	$\leq 100$	$\leq 10000$

时间限制： $1 s$

空间限制： $512 MB$

中国国家队清华集训2014~2015 Day 2 - By 彭天翼

Universal Online Judge