题意：
有个N X M的棋盘， 有K种颜色， 有B个不可涂色的位置， 共有R种涂色方案。
1）每个可涂色的位置必须涂上一种颜色
2）不可涂色位置不能涂色
3）每个位置必须从K种颜色中选出一种颜色进行涂色
4）当前格子(x,y) 上面的那个格子(x+1,y)不能同色
现在已知N, K, B, R， 求满足条件的最小的M
思路：
B个不可涂色位置设为(x1, y1), (x2, y2), (x3, y3), ... , (xb, yb)
1）M必然 ≥ max(x[i])
2）设前max(x[i]) 行 与 max(x[i]) + 1 行涂色方案为 cnt， 则 max(x[i]) + 1之后的每一行， 涂色方案都是 (K-1)^N。
3）设P = (K - 1) ^ N
存在一个j 使得：
cnt * P^j = R
右乘cnt的逆元 cnt ^ -1 得：
P^j = R * cnt ^ -1
即求一个最小的j满足上式。
P^j ≡ R * cnt ^ -1 (mod MOD) , MOD = 100000007
利用对数取余进行求解
代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
using namespace std;
#define LL long long
#define MAXN 550
#define MOD 100000007
int n, b, r, k, m;
int x[MAXN], y[MAXN];
set<pair<int, int> > best; void ex_gcd(LL a, LL b, LL& d, LL& x, LL& y)
{
if(!b) {d = a; x = ; y = ;}
else
{ex_gcd(b, a%b, d, y, x); y -= x*(a/b);}
} LL inv(LL a)
{
LL d, x, y;
ex_gcd(a, MOD, d, x, y);
return d == ?(x + MOD) % MOD : -;
} LL mul_mod(LL a, LL b)
{
return a * b % MOD;
} LL pow_mod(LL a, LL p)
{
if(p == ) return ;
LL ans = pow_mod(a, p/);
ans = ans * ans % MOD;
if(p % == ) ans = ans * a % MOD;
return ans;
} int log_mod(int a, int b)
{
int m, v, e = , i;
m = (int)sqrt(MOD+0.5);
v = inv(pow_mod(a, m));
map<int, int> x;
x[] = ;
for (int i = ; i < m; i++)
{
e = mul_mod(e, a);
if (!x.count(e))
x[e] = i;
}
for (int i = ; i < m; i++)
{
if (x.count(b))
return i*m + x[b];
b = mul_mod(b, v);
}
return -;
} int solve()
{
int cur = ;
int cnt = ; for(int i = ; i < b; i ++)
if(x[i] != m && !best.count(make_pair(x[i] + , y[i]))) cur ++;
cur += n;
for(int i = ; i < b; i ++)
if(x[i] == ) cur --; // ans = k^cur * (k-1) ^ (n*m - b - cur);
cnt = mul_mod(pow_mod(k, cur), pow_mod(k - , (LL)n * m - b - cur)); if(cnt == r) return m; cur = ;
for(int i = ; i < b; i ++)
if(x[i] == m) cur ++; //ans = cnt * k^cur * (k - 1)^(n - cur);
cnt = mul_mod(cnt, pow_mod(k, cur));
cnt = mul_mod(cnt, pow_mod(k - , n - cur));
m ++; if(cnt == r) return m; //printf("%d %d %d\n", pow_mod(k - 1, n), inv(cnt), log_mod(pow_mod(k - 1, n), mul_mod(r, inv(cnt))));
// P = (k - 1) ^ n, P^x = r * cnt^-1;
return log_mod(pow_mod(k - , n), mul_mod(r, inv(cnt))) + m;
} int main()
{
int T;
scanf("%d", &T);
for(int kcase = ; kcase <= T; kcase ++)
{
scanf("%d %d %d %d", &n, &k, &b, &r);
best.clear();
m = ;
for(int i = ; i < b; i ++)
{
scanf("%d %d",&x[i], & y[i]);
m = max(m, x[i]);
best.insert(make_pair(x[i], y[i]));
}
printf("Case %d: %d\n", kcase, solve());
}
return ;
}
这题WA了一天， 反复找错都没找到， 重写第N + 1次的时候终于找到错误 ， 求逆函数写错了 囧