F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 4587. -- 推箱子

4587: 推箱子

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 44  Solved: 5
[Submit][Status][Discuss]

Description

二维平面上有一个可以活动的箱子位于 (0,0)  ,现在可以对它施加三种操作:
向右方推, 横坐标增加 1
向上方推 ,纵坐标增加 1
向右上方推,横纵坐标均增加 1
而平面上还有 k 个不可活动的箱子位于第一象限的一些整点上,
活动的箱子不能推到这些整点上。可能存在一些不可活动的箱子位于同一个点,可以认为它们垒在了一起。现在希
望将活动的箱子推到直线 x=n 或直线 y=m 上并立即停止活动,问有多少种推法,答案对 p 取模。两种推法视为
相同的,当且仅当它们的操作次数相等且每一次的操作相等。

Input

第一行有一个正整数 t ,表示数据组数。
对于每组测试数据:
第一行有四个非负整数 n,m,k,p ,相邻数字间有一个空格。
接下来 k 行,每行有两个正整数 a,b ,表示一个不可活动的箱子位于 (a,b)  ,相邻数字间有一个空格。
保证 1≤a≤n,1≤b≤m 。 t≤2000,tot≤10^5,1≤N≤10^4,1≤M≤10^9,0≤k≤10,1≤p<2^31

Output

共 t 行,每行对应一组测试数据,为一个非负整数表示答案对 p 取模后的值。

Sample Input

3
1 1 0 100
1 1 1 100
1 1
3 3 2 100
1 1
2 2

Sample Output

3
2
12
【样例解释】
对于第二组测试数据,满足条件的推法只有两种,分别是一次向右推,和一次向上推。
对于第三组测试数据,满足条件的推法都无法推到 (n,m)

HINT

Source

By Tangjz

[Submit][Status][Discuss]

HOME Back