HDU 4518 吉哥最終數：AC自動機 + 數位DP + 二分查找

問題描述

定義 F數：十進制表示中包含至少一個 ≥10 的斐波那契數（13, 21, 34, 55, 89, 144...）作為子串。最終數：在 F數序列中，下標也是斐波那契數的那些 F數。給定 n (≤ 10^11)，求離 n 最近的最終數與 n 的差的絕對值。

解法框架

1. 生成斐波那契數列 `fib[]`（到 > 10^11）。
2. 將所有 ≥10 的斐波那契數插入 AC 自動機，構建失敗指針與輸出標記。
3. 數位 DP：`dfs(pos, state, tight)` 返回長度為 pos、自動機狀態為 state、是否受上界限制的合法數個數（含至少一個斐波那契子串）。利用 `end[state]` 標記是否已匹配到模式。
4. 對每個斐波那契下標 `fib[i]`，在數值域 [13, 10^12] 上二分查找最小的 x 使得 `count(x) >= fib[i]`，該 x 即為第 `fib[i]` 個 F數，即最終數。預計算所有最終數存入 `seq[]`。
5. 查詢時遍歷 `seq[]` 找最小 `|n - seq[i]|`。

關鍵代碼片段

struct Trie {
    int next[1010][10], end[1010], fail[1010];
    int root, L;
    void init() { L = 0; root = newnode(); }
    int newnode() { ... }
    void insert(int x) { ... } // 從低位向高位插入
    void build() { ... } // BFS 構建 fail，合併 end 標記
} ac;

long long dp[15][1010], suf[15], num[15], POW[20];

long long dfs(int pos, int st, bool flag) {
    if (pos == 0) return 0;
    if (flag && dp[pos][st] != -1) return dp[pos][st];
    int u = flag ? 9 : num[pos];
    long long ans = 0;
    for (int i = 0; i <= u; i++) {
        int nst = ac.next[st][i];
        if (ac.end[nst]) {
            if (flag || i < u) ans += POW[pos - 1];
            else ans += suf[pos - 1] + 1;
        } else ans += dfs(pos - 1, nst, flag || i < u);
    }
    if (flag) dp[pos][st] = ans;
    return ans;
}

long long cal(long long x) { // 計算 ≤x 的 F數個數
    // 分解數位到 num[], 計算 suf[] 前綴值
    return dfs(len, ac.root, 0);
}

// 主程序預計算 seq[i] (i=2..56)
for (int i = 2; i <= 56; i++) {
    long long l = 13, r = POW[12];
    while (l < r) {
        long long mid = (l + r) / 2;
        if (cal(mid) < fib[i]) l = mid + 1;
        else r = mid;
    }
    seq[i] = l;
}

關鍵技巧

• AC 自動機匹配多模式：將所有斐波那契數（≥10）作為模式串插入，`end` 標記該狀態或其失敗鏈上是否為模式結尾。
• 數位 DP 狀態：位置、自動機狀態、是否受限。轉移時枚舉當前位數字，更新自動機狀態。若新狀態 `end` 為真，後續位任意填（`POW` 或 `suf` 直接計數），否則遞歸。
• 二分查找第 k 個 F數：`cal(x)` 為 ≤x 的 F數計數，單調遞增，二分找最小 x 使 `cal(x) >= k`。
• 預計算最終數：斐波那契下標只到 56 即覆蓋 10^11 範圍，離線預計算 `seq[]`，查詢 O(1)。

複雜度

• AC 自動機節點數 ≈ 總模式長度 < 1000。
• DP 狀態：位數(≤12) × 狀態數(≤1000) × 2 ≈ 24000，極快。
• 預計算 55 次二分，每次 log(10^12) ≈ 40 步 DP，總計毫秒級。
• 查詢：遍歷 55 個最終數，O(1)。