程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11916 - Emoogle Grid(大步小步算法)

uva 11916 - Emoogle Grid(大步小步算法)

編輯：C++入門知識

題目連接：uva 11916 - Emoogle Grid

題目大意：有一問題，在M行N列的網格上塗K種顏色，其中有B個格子不用塗色，其它每個格子塗一種顏色，同一列的上下兩個相鄰的格子不能塗相同的顏色。給出M，N，K和B個格子的位置，求出總方案數模掉1e8+7的結果R。現在已知R，求最小的M。

解題思路：有確定不用塗色格子的區域作為不變部分，總數通過計算為tmp，外加可變部分的第一行，方案數為cnt，可變部分除第一行外，每加一行都將總數乘以(K?1)N,既有

cnt?PM=Rmod(1e8+7)

PM=cnt?1?Rmod(1e8+7)
就是大步小步算法求M。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const ll MOD = 1e8+7;
const int maxn = 505;

int N, M, K, R, B, X[maxn], Y[maxn];
set > bset;

inline ll mul_mod (ll a, ll b) {
    return (ll)a * b % MOD;
}

inline ll pow_mod (ll a, ll n) {
    ll ans = 1;
    while (n) {
        if (n&1)
            ans = mul_mod(ans, a);
        a = mul_mod(a, a);
        n /= 2;
    }
    return ans;
}

void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
    if (!b) {
        d = a;
        x = 1;
        y = 0;
    } else {
        gcd (b, a%b, d, y, x);
        y -= x * (a/b);
    }
}

inline ll inv (ll a) {
    ll d, x, y;
    gcd(a, MOD, d, x, y);
    return d == 1 ? (x+MOD)%MOD : -1;
}

void init () {
    scanf("%d%d%d%d", &N, &K, &B, &R);
    bset.clear();
    M = 1;
    for (int i = 0; i < B; i++) {
        scanf("%d%d", &X[i], &Y[i]);

        M = max(M, X[i]);

        bset.insert(make_pair(X[i], Y[i]));
    }
}

int count () {
    int c = 0;
    for (int i = 0; i < B; i++) {
        if (X[i] != M && !bset.count(make_pair(X[i]+1, Y[i])))
            c++;
    }

    c += N;
    for (int i = 0; i < B; i++)
        if (X[i] == 1)
            c--;

    return mul_mod(pow_mod(K, c), pow_mod(K-1, (ll)M*N-B-c));
}

int log_mod (ll a, ll b) {
    ll m = (ll)sqrt(MOD+0.5), v, e = 1;
    v = inv(pow_mod(a, m));
    map g;

    g[1] = 0;

    for (ll i = 1; i < m; i++) {
        e = mul_mod(e, a);
        if (!g.count(e))
            g[e] = i;
    }

    for (ll i = 0; i < m; i++) {
        if (g.count(b))
            return i*m+g[b];
        b = mul_mod(b, v);
    }
    return -1;
}

int doit () {
    int cnt = count();

    if (cnt == R)
        return M;

    int c = 0;
    for (int i = 0; i < B; i++)
        if (X[i] == M)
            c++;

    M++;
    cnt = mul_mod(cnt, pow_mod(K, c));
    cnt = mul_mod(cnt, pow_mod(K-1, N-c));

    if (cnt == R)
        return M;

    return log_mod(pow_mod(K-1, N), mul_mod(R, inv(cnt))) + M;
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        init();
        printf("Case %d: %d\n", i, doit());
    }
    return 0;
}