OI题库

【题目描述】

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

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

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

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

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

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

                                 

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

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

【输入格式】

输入包含多组数据。

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

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

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

接下来有B行，每行包含两个正整数x,y(1<=x<=M,1<=y<=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<=M<=1000

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

【来源】

UVa11916 Emoogle Grid

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