UVA 11916 Emoogle Grid (BSGS)

題意：原問題是有M*N個方格，K種顔色，有B個方格不能塗色，且垂直相連的兩個方格不能塗同一種顔色。問有多少種塗色方案。現在問題改為已知N,K,B以及原問題的結果r求最小的可能的M。

題解：BSGS

首先考慮沒有不能塗色的方格的情況，那麼第一行的每一個方格都可以任意塗色，就是kn，而剩餘的方格除了對應的上一行的顔色都可以随意填，(k - 1)^(n * m - n)，兩式相乘就是答案。

當出現了不能填顔色的方格時，如果它的下面有方格，這個方格就可以任意塗色了。這個時候判斷一下多少個方格可以塗k種顔色，多少個方格可以塗k-1種顔色。

求最小行數時要用到BSGS （a^x≡b(mod p)中x的最小值）

具體看代碼注釋。

注意模數是1e8+7。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const int mod = 1e8 + 7;
ll t, n, k, b, r, x, y;
struct node {
	ll a, b;
	node() {}
	node(int a, int b) :a(a), b(b) {}
	bool operator<(const node m)const {
		return b == m.b ? a < m.a : b < m.b;
	}
}block[555];
ll quick_pow(ll a, ll b) {
    ll res = 1, tmp = a;
    while (b) {
        if (b & 1) res = res * tmp % mod;
        tmp = tmp * tmp % mod;
        b >>= 1;
    }
    return res;
}
void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    }
    else {
        exgcd(b, a % b, d, y, x);
        y -= a / b * x;
    }
}
ll BSGS(ll a, ll b, ll p) {
    ll m = (ll)ceil(sqrt(p + 0.5));
    map<ll, int> rid;
    ll tmp = 1;
    for (int i = 0; i < m; ++i) {
        if (rid.find(tmp) == rid.end()) rid[tmp] = i; //需要判斷是否已經出現過
        tmp = tmp * a % p;
    }
    ll tmp2 = quick_pow(tmp, p - 2); //模質數求逆元
    for (int i = 0; i < m; ++i) {
        if (rid.find(b) != rid.end()) return rid[b] + i * m;
        b = b * tmp2 % p;
    }
}

int main() {
	scanf("%d", &t);
    int cas = 0;
	while (t--) {
		scanf("%lld%lld%lld%lld", &n, &k, &b, &r);
        ll maxr = 1; //注意初始化
		for (int i = 1; i <= b; i++) {
			scanf("%d%d", &x, &y);
			block[i] = node(x, y);
            maxr = max(maxr, x);
		}
        sort(block + 1, block + b + 1);
        ll num = 0, bottom = 0;  //num為可以塗k個顔色的數量
        for (int i = 1; i <= b; i++) {
            if (block[i].a > 1) {
                if (i == 1) num++;
                else if (block[i - 1].b != block[i].b) num++;
                else if (block[i - 1].a + 1 != block[i].a) num++;
            }
            if (block[i].a == maxr) bottom++;
        }
        num += n - bottom;
        //temp為答案
        ll temp = quick_pow(k, num) * quick_pow(k - 1, n * maxr - b - num) % mod;
        if (temp == r) {  //答案剛好滿足
            printf("Case %d: %lld\n", ++cas, maxr);
            continue;
        }
        //不滿足，繼續增加行數
        //先增加一行（maxr + 1）得到的答案
        temp = temp * quick_pow(k, bottom) % mod * quick_pow(k - 1, n - bottom) % mod;
        ll x, y, d;
        exgcd(temp, mod, d, x, y);
        x = (x * (r / d) % mod + mod) % mod;  //注意x為負數情況
        ll ans = BSGS(quick_pow(k - 1, n), x, mod);  //求還需要的最小行數ans
        printf("Case %d: %lld\n", ++cas, ans + maxr + 1);
    }
	return 0;
}