[DMOI-R2] 回到过去

ID: 8060

远端评测题

3000ms

256MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

标签>

O2优化

组合数学

容斥

题目背景

想回到过去
试着抱你在怀里
羞怯的脸带有一点稚气
想看你看的世界
想在你梦的画面
只要靠在一起就能感觉甜蜜
想回到过去
试着让故事继续
至少不再让你离我而去
分散时间的注意
这次会抱得更紧
这样挽留不知还来不来得及
想回到过去
沉默支撑跃过陌生
静静看着凌晨黄昏
你的身影失去平衡
慢慢下沉
想回到过去
—— 周杰伦《回到过去》

什么阻碍着两颗心的碰面？什么阻碍着两个人的相见？

或许是令人捉摸不透的时间吧。

题目描述

给出 $n,m,t$ 以及 $t$ 个障碍物坐标，求在 $n$ 行 $m$ 列的矩阵中的非障碍位置上放置 $k$ 个两两之间没有公共边的方格的方案有多少种，答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行一个整数 $T$ ，表示测试点数量。

接下来 $T$ 个测试点，每个测试点的第一行四个整数 $n,m,k,t$ 。接下来 $t$ 行，每行两个整数 $x_i,y_i$ ，表示第 $i$ 个障碍物的坐标（保证不重叠）。

输出格式

共 $T$ 行，每行一个整数表示当前询问的答案。

输入数据 1

输出数据 1

输入数据 2

10
4329 12935 3 0
125891 5949823 2 0
95023489 15327384 3 0
28592394 32891538 2 0
5894392 52374853 2 0
58963495 32591238 3 0
438291538 42819324 3 0
58493683 234728 2 0
284952 823499 3 0
528394298 25892948 3 0

输出数据 2

输入数据 3

10
55888076 506356561 3 3
48940088 192152177
33004718 365781091
45088097 31400730
65004621 206038505 2 3
50919157 24882066
50919158 24882064
50919156 24882067
249418509 7616530 2 1
205309921 4639136
164784593 419325145 3 4
105814446 200482317
105814449 200482315
105814443 200482315
79723922 206425705
477366546 180501076 3 4
39819749 14485585
39819746 14485582
39819743 14485588
39819748 14485585
84215455 29656489 3 0
524291275 23244413 3 4
8149961 10903189
8149958 10903192
8149958 10903193
8149961 10903191
584987873 823324694 3 1
540008401 27919189
25681672 419244427 2 4
4753299 108169462
4753301 108169463
4753298 108169462
4753298 108169464
313195991 98402123 3 3
7016773 83186671
7016770 83186674
7016767 83186675

输出数据 3

输入数据 4

输出数据 4

提示

【样例解释 #4】

对于测试点 1，可以画出如下的图：

其中用黑色格子表示障碍物，可发现只有 $\{(1,2)(1,4)\}\{(1,2)(2,3)\}\{(2,2)(1,4)\}\{(2,3)(1,4)\}$ 四种方案满足题意。

对于测试点 2，可以画出如下的图：

可发现只有 $\{(1,1)(1,3)(2,2)\}\{(1,1)(1,3)(2,4)\}\{(1,1)(2,2)(2,4)\}\{(1,3)(2,1)(2,4)\}\{(1,3)(2,2)(2,4)\}$ 五种情况符合题意。

数据点约定

数据点编号	$n$	$m$	$k$	$t$
$1$	$=1$	$\le 10^9$	$=2$	$=0$
$2$	$=1$	$\le 10^9$	$=3$
$3$	$\le 20$		$=2$
$4$			$=3$
$5$			$=2$	$\le 400$
$6$			$=3$	$\le 400$
$7,8$	$\le 1000$		$=2$	$=0$
$9,10$			$=3$	$=0$
$11$			$=2$	$\le 10$
$12$			$=3$	$\le 10$
$13,14$	$\le 10^9$	$=n$	$=2$	$=0$
$15,16$		$=n$	$=3$
$17,18$		$\le 10^9$	$=2$
$19,20$			$=3$
$21,22$			$=2$	$\le 2 \times 10^4$
$23,24$			$=3$
$25$			$2 \le k \le 3$

对于 $100\%$ 的数据， $1 \le n,m \le 10^9$ ， $2 \le k \le 3$ ， $0 \le t \le \min(n\cdot m,2 \times 10^4)$ ， $1 \le x_i \le n$ ， $1 \le y_i \le m$ ， $1 \le T \le 10$ 。每个数据点等分值。

#P8915. [DMOI-R2] 回到过去