UVA 11916 Emoogle Grid 大步小步算法求解

問題重述

M×N 網格，K 種顏色，B 個格子不塗色。同列相鄰格子顏色不同。已知總方案數 R = 總方案數 mod (1e8+7)，求最小 M。

數學建模

固定部分（前 M 行含不塗色格子）方案數為 tmp，第 M+1 行（可變部分首行）方案數為 cnt，其後每行乘以 (K-1)^N。即：

cnt × (K-1)^(N×(M'-M)) ≡ R (mod MOD)

設 P = (K-1)^N mod MOD，則需解 cnt × P^x ≡ R，即離散對數問題 P^x ≡ R × cnt^{-1}，用 BSGS（大步小步）求解 x，答案 M' = M + x。

算法步驟

1. 統計固定區域（含不塗色格子）的方案數 tmp 及首行可變格子數 cnt
2. 若 tmp == R 直接返回 M
3. 擴展一行：更新 M，重新計算 cnt（考慮新行與上一行的約束）
4. 若仍不等，用 BSGS 求解剩餘行數

BSGS 核心實現

int log_mod(ll a, ll b) { // 求 a^x ≡ b (mod MOD)
    ll m = sqrt(MOD) + 1, v, e = 1;
    v = inv(pow_mod(a, m)); // a^{-m}
    unordered_map g; g[1] = 0;
    for (ll i = 1; i < m; i++) { e = e * a % MOD; if (!g.count(e)) g[e] = i; }
    for (ll i = 0; i < m; i++) {
        if (g.count(b)) return i*m + g[b];
        b = b * v % MOD;
    }
    return -1;
}

模逆用擴展歐幾里得，模冪用快速冪。注意 MOD = 1e8+7 為質數，逆元存在。