网格涂色

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file emoogle.in Output file emoogle.out

【题目描述】

你要给一个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