1483. [UVa 11916] 网格涂色

【题目描述】

你要给一个 $M*N(1 \leq M,N \leq 10^8)$ 的二维网格用 $K(2 \leq K \leq 10^8)$ 种颜色染色。将给出 $B(0 \leq B \leq 500)$ 个被堵上的格子，这些格子不能涂色。我们用 $(x,y)$ 代表第 $x$ 行第 $y$ 列的格子。

当给网格涂色时，你必须遵循如下规则：

$1$.你必须给所有未被堵上的格子涂色。

$2$.你不能给堵上的格子涂色。

$3$.你可以从 $K$ 种颜色中选一种，给某个格子涂色。

$4$.同一列中上下相邻的两个格子不能涂相同的颜色，即格子 $(x,y)$ 和格子 $(x+1,y)$ 不能涂相同的颜色。

在这里，伟大的出题人激动地笑了笑，想到要求参赛者们计算给网格染色的方案总数。因为这个数可能很大，并且他不想让参赛者们在处理大整数时遇到困难，所以他决定要求参赛者们计算方案总数模 $100,000,007$ 的值 $R$。他于是用随机数生成器造了测试数据，并且把这个题目保存下来，准备在未来的比赛中当做送分题。

不幸的是，他结婚了，（在给妹子全家修理电脑手机 $MP4$ 的繁杂事务中——译者注）完全忘掉了这道题。若干天后，他兴奋地重新发现了自己出的题目。但过了一会，他发现自己忘记了在测试数据中加入行数。他没有找到输入数据生成器和解答代码，但幸运地，他找到了输入输出数据。因此，他要求你帮忙生成数据。没错，给你包含了除行数外所有信息的输入文件和输出文件，要求你给出可能的行数。

【输入格式】

输入包含多组数据。

输入文件的第 $1$ 行有一个正整数 $T(T \leq 150)$，表示数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

第 $1$ 行有 $4$ 个正整数：$N,K,B,R(0 \leq R < 100000007)$，其中 $R$ 表示这组数据的结果（即染色方案数模$100000007$的值）。

接下来有 $B$ 行，每行包含两个正整数 $x,y(1 \leq x \leq M,1 \leq y \leq N)$，描述一个堵上的格子。输入保证这些被堵上的格子两两不同。

【输出格式】

对于每组数据，输出 $M$ 的最小可能值。输入保证一定有解。

【样例输入】

4
3 3 0 1728 4 4 2 186624
3 1
3 3
2 5 2 20
1 2
2 2
2 3 0 989323

【样例输出】

Case 1: 3
Case 2: 3
Case 3: 2
Case 4: 20

【提示】

对于 $30\%$ 的数据，$1 \leq M \leq 1000$；

对于 $100\%$ 的数据，所有数据规模均如题中所述。

【来源】

UVa 11916 Emoogle Grid

刘汝佳，《算法竞赛入门经典训练指南》表2.4