题意:
有个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
利用对数取余进行求解
代码如下:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 using namespace std;
16 #define LL long long
17 #define MAXN 550
18 #define MOD 100000007
19 int n, b, r, k, m;
20 int x[MAXN], y[MAXN];
21 set<pair<int, int> > best;
22
23 void ex_gcd(LL a, LL b, LL& d, LL& x, LL& y)
24 {
25 if(!b) {d = a; x = 1; y = 0;}
26 else
27 {ex_gcd(b, a%b, d, y, x); y -= x*(a/b);}
28 }
29
30 LL inv(LL a)
31 {
32 LL d, x, y;
33 ex_gcd(a, MOD, d, x, y);
34 return d == 1?(x + MOD) % MOD : -1;
35 }
36
37 LL mul_mod(LL a, LL b)
38 {
39 return a * b % MOD;
40 }
41
42 LL pow_mod(LL a, LL p)
43 {
44 if(p == 0) return 1;
45 LL ans = pow_mod(a, p/2);
46 ans = ans * ans % MOD;
47 if(p % 2 == 1) ans = ans * a % MOD;
48 return ans;
49 }
50
51 int log_mod(int a, int b)
52 {
53 int m, v, e = 1, i;
54 m = (int)sqrt(MOD+0.5);
55 v = inv(pow_mod(a, m));
56 map<int, int> x;
57 x[1] = 0;
58 for (int i = 1; i < m; i++)
59 {
60 e = mul_mod(e, a);
61 if (!x.count(e))
62 x[e] = i;
63 }
64 for (int i = 0; i < m; i++)
65 {
66 if (x.count(b))
67 return i*m + x[b];
68 b = mul_mod(b, v);
69 }
70 return -1;
71 }
72
73 int solve()
74 {
75 int cur = 0;
76 int cnt = 0;
77
78 for(int i = 0; i < b; i ++)
79 if(x[i] != m && !best.count(make_pair(x[i] + 1, y[i]))) cur ++;
80 cur += n;
81 for(int i = 0; i < b; i ++)
82 if(x[i] == 1) cur --;
83
84 // ans = k^cur * (k-1) ^ (n*m - b - cur);
85 cnt = mul_mod(pow_mod(k, cur), pow_mod(k - 1, (LL)n * m - b - cur));
86
87 if(cnt == r) return m;
88
89 cur = 0;
90 for(int i = 0; i < b; i ++)
91 if(x[i] == m) cur ++;
92
93 //ans = cnt * k^cur * (k - 1)^(n - cur);
94 cnt = mul_mod(cnt, pow_mod(k, cur));
95 cnt = mul_mod(cnt, pow_mod(k - 1, n - cur));
96 m ++;
97
98 if(cnt == r) return m;
99
100 //printf("%d %d %d\n", pow_mod(k - 1, n), inv(cnt), log_mod(pow_mod(k - 1, n), mul_mod(r, inv(cnt))));
101 // P = (k - 1) ^ n, P^x = r * cnt^-1;
102 return log_mod(pow_mod(k - 1, n), mul_mod(r, inv(cnt))) + m;
103 }
104
105 int main()
106 {
107 int T;
108 scanf("%d", &T);
109 for(int kcase = 1; kcase <= T; kcase ++)
110 {
111 scanf("%d %d %d %d", &n, &k, &b, &r);
112 best.clear();
113 m = 1;
114 for(int i = 0; i < b; i ++)
115 {
116 scanf("%d %d",&x[i], & y[i]);
117 m = max(m, x[i]);
118 best.insert(make_pair(x[i], y[i]));
119 }
120 printf("Case %d: %d\n", kcase, solve());
121 }
122 return 0;
123 }
这题WA了一天, 反复找错都没找到, 重写第N + 1次的时候终于找到错误 , 求逆函数写错了 囧