题意：用K种颜色给一个N*M的格子涂色。其中有B个格子是不能涂色的。涂色时满足同一列上下紧邻的两个格子的颜色不同。所有的涂色方案模100000007后为R。现在给出M、K、B、R，求一个最小的N，满足题意。
思路：分成两个部分。设给出的B个不能涂的格子的最大行坐标为m。 首先，我们能计算出前m行的方案数cnt，若cnt=r，则m就是答案。每增加一行，就会增加（K-1）^m种方法,接着令p=(K-1)^M，我们能计算出前m+1行的方案数cnt，若cnt=r 则答案为 m+1。否则，设下面还需要t行，那么有cnt*(p)^t%100000007=R，将cnt的逆元乘到右侧得到新的 p^t=R*reverse(cnt)。那么就成了求最小的t满足p^t%100000007=R*reverse(cnt)。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
using namespace std; const int MOD = ;
const int maxb = + ;
int n, m, k, b, r, x[maxb], y[maxb];
set<pair<int, int> > bset; int pow_mod(int a, long long p)
{
if(p == )
return ;
int ans = pow_mod(a, p/);
ans = (long long)ans * ans % MOD;
if(p%)
ans = (long long)ans * a % MOD;
return ans;
} int mul_mod(int a, int b)
{
return (long long)a * b % MOD;
} int inv(int a)
{
return pow_mod(a, MOD-);
} int log_mod(int a, int b)
{
int m, v, e = , i;
m = (int)sqrt(MOD);
v = inv(pow_mod(a, m));
map <int,int> x;
x[] = ;
for(i = ; i < m; i++)
{
e = mul_mod(e, a);
if (!x.count(e)) x[e] = i;
}
for(i = ; i < m; i++)
{
if(x.count(b)) return i*m + x[b];
b = mul_mod(b, v);
}
return -;
} // 计算可变部分的方案数
int count()
{
int c = ; // 有k种涂法的格子数
for(int i = ; i < b; i++)
{
if(x[i] != m && !bset.count(make_pair(x[i]+, y[i]))) c++; // 不可涂色格下面的可涂色格
}
c += n; // 第一行所有空格都有k种涂法
for(int i = ; i < b; i++)
if(x[i] == ) c--; // 扣除那些不能涂色的格子 // ans = k^c * (k-1)^(mn - b - c)
return mul_mod(pow_mod(k, c), pow_mod(k-, (long long)m*n - b - c));
} int doit()
{
int cnt = count();
if(cnt == r) return m; // 不变部分为空 int c = ;
for(int i = ; i < b; i++)
if(x[i] == m)
c++; // 可变部分第一行中有k种涂法的格子数
m++; // 多了一行（可变部分的第一行）
cnt = mul_mod(cnt, pow_mod(k, c));
cnt = mul_mod(cnt, pow_mod(k-, n - c));
if(cnt == r) return m; // 此时cnt为不变部分和可变部分第一行的方案总数 return log_mod(pow_mod(k-,n), mul_mod(r, inv(cnt))) + m;
} int main()
{
int T;
scanf("%d", &T);
for(int t = ; t <= T; t++)
{
scanf("%d%d%d%d", &n, &k, &b, &r);
bset.clear();
m = ;
for(int i = ; i < b; i++)
{
scanf("%d%d", &x[i], &y[i]);
if(x[i] > m) m = x[i]; // 更新不变部分的行数
bset.insert(make_pair(x[i], y[i]));
}
printf("Case %d: %d\n", t, doit());
}
}