您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 11645 - Bits：數位 DP 計算 0~n 二進制中連續 "11" 的總數

編輯：C++ 入門

問題重述

給定 n (≤ 10¹⁸)，求所有整數 0 ~ n 的二進制表示中，子串 "11" 出現的總次數。答案可能超過 64 位整數範圍。

解題思路：逐位貢獻法 + 高精度加法

考慮第 k 位（從低到高，0-based）作為「第二個 1」的位置，即模式 ...11 中較高的那個 1。枚舉該位為 1 的所有數字，統計其低位組合數：

高位部分（第 k+1 位以上）可取 0 ~ high，共 high 種完整循環，每循環貢獻 2ᵏ 次
若 n 的第 k 位與 k-1 位均為 1，則最後一個不完整循環額外貢獻 low + 1 次（low 為第 k-1 位以下的值）

累加各位貢獻即得答案。因答案可能極大，採用 雙 long long 模擬 10¹³ 進制：a 儲存高段，b 儲存低 13 位，加法時處理進位。

關鍵代碼

const long long DIG = 1e13;
long long a = 0, b = 0;

void add(long long num) {
    b += num;
    a += b / DIG;
    b %= DIG;
}

int main() {
    long long n; int cas = 0;
    while (~scanf("%lld", &n) && n >= 0) {
        a = b = 0;
        long long tmp = n, d = 1;
        while (n > 1) {
            add((n >> 2) * d);
            if ((n & 3) == 3) add((tmp & (d - 1)) + 1);
            d <<= 1;
            n >>= 1;
        }
        printf("Case %d: ", ++cas);
        if (a) printf("%lld%013lld\n", a, b);
        else printf("%lld\n", b);
    }
    return 0;
}