UVA 11916 Emoogle Grid：離散對數解矩陣著色計數

問題描述

M×N 矩陣，K 種顏色，B 個禁色格。每格顏色不能與上方格相同。已知 N 和總方案數 R（模 100,000,007），求最小滿足條件的行數 M。

數學建模

設最大禁色行為 maxX。分三段：

1. 前 maxX 行：受禁色影響，逐列獨立計算方案數。
2. 第 maxX+1 行：消除禁色邊界影響。
3. 剩餘 T = M - maxX - 1 行：每格只有 K-1 種選擇（不可與上方同色）。

總方案數 ans = front * (K-1)^(T*N) ≡ R (mod MOD)。求 T 即離散對數問題 A^T ≡ B (mod MOD)。

離散對數（Baby-Step Giant-Step）

ll log_mod(ll a, ll b) {
    ll m = sqrt(mod) + 1;
    unordered_map mp;
    ll e = 1;
    for (ll i = 0; i < m; ++i) {
        if (!mp.count(e)) mp[e] = i;
        e = e * a % mod;
    }
    ll v = inv(pow_mod(a, m));
    ll cur = b;
    for (ll i = 0; i < m; ++i) {
        if (mp.count(cur)) return i * m + mp[cur];
        cur = cur * v % mod;
    }
    return -1;
}

完整流程

1. 讀入禁色格，統計 maxX 及該行禁色數 maxcnt。
2. 計算前 maxX 行方案數 ans：每列獨立，段落長度為連續非禁色格數。
3. 若 ans == R 直接返回 maxX。
4. 乘上第 maxX+1 行方案數，若等於 R 返回 maxX+1。
5. 否則解離散對數得 T，答案 maxX+1+T。

複雜度

BSGS O(√MOD) ≈ 10⁴，極快。整體 O(B log B + √MOD)。