UVa 11916 (离散对数) Emoogle Grid

因为题目要求同列相邻两格不同色，所以列与列之间不影响，可以逐列染色。

如果一个格子的上面相邻的格子，已经被染色则染这个格子的时候，共有k-1中选择。

反过来，如果一个格子位于第一列，或者上面相邻的格子是不能被染色的格子，则共有k中选择。

虽然，矩阵的行数不定，但至少为所有不能被染色格子行标的最大值m。

分别检验一下染m行和m+1行的方案数(mod 100000007)是否为r

否则的话，后面每染一行方案数都会乘p = (k-1)ⁿ，假设前面计算出来的m+1行方案数为cnt

下面的任务就是求解 p^x * cnt = r (mod MOD)，两边乘cnt的逆，得 p^x = r * cnt^-1 (mod MOD)

最后加上前面的m+1行，答案为x + m + 1

最后吐槽一下我认为的坑点=_=，看到那个模想当然地以为是1e9+7，但是最后一个样例调了好久没过，后来才发现题中给的模是1e8+7

 #include <cstdio>

 #include <map>

 #include <set>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define MP make_pair

 #define INS insert

 typedef long long LL;

 const int MOD = ;

 const int maxb =  + ;

 int n, m, k, b, r, x[maxb], y[maxb], fir_row;

 set<pair<int, int> > Set;

 int mul_mod(int a, int b)

 { return (LL) a * b % MOD; }

 int pow_mod(int a, LL n)

 {

     int ans = , base = a;

     while(n)

     {

         if(n & ) ans = mul_mod(ans, base);

         base = mul_mod(base, base);

         n >>= ;

     }

     return ans;

 }

 int inv(int a)

 { return pow_mod(a, MOD - ); }

 int log_mod(int a, int b)

 {//a^x=b (mod MOD)

     int m, v, e = , i;

     m = (int)sqrt(MOD + 0.5);

     v = inv(pow_mod(a, m));

     map<int, int> x;

     x[] = ;

     for(i = ; i < m; i++)

     {

         e = mul_mod(e, a);

         if(e == b) return i;

         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 solve()

 {

     int c = ;//前m行涂k种颜色的格子个数

     for(int i = ; i < b; i++)

         if(x[i] != m && !Set.count(MP(x[i] + , y[i]))) c++;

     c += n - fir_row;

     int cnt = mul_mod(pow_mod(k, c), pow_mod(k-, (LL)m*n - b - c));

     if(cnt == r) return m;

     c = ;//第m+1行涂k种颜色的格子个数

     for(int i = ; i < b; i++) if(x[i] == m) c++;

     cnt = mul_mod(mul_mod(cnt, pow_mod(k, c)), pow_mod(k-, n-c));

     if(cnt == r) return m + ;

     int p = pow_mod(k-, n);

     int v = inv(cnt);

     return log_mod(p, mul_mod(r, v)) + m + ;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%d%d%d%d", &n, &k, &b, &r);

         Set.clear();

         m = ; fir_row = ;

         for(int i = ; i < b; i++)

         {

             scanf("%d%d", &x[i], &y[i]);

             Set.INS(MP(x[i], y[i]));

             if(x[i] > m) m = x[i];

             if(x[i] == ) fir_row++;//第一行不能被涂色的个数

         }

         printf("Case %d: %d\n", kase, solve());

     }

     return ;

 }

代码君

巴特西

UVa 11916 (离散对数) Emoogle Grid

最新文章

热门文章