HDU 2502 題解：月之數——二進制位計數規律

題目大意

給定 m，考慮所有 m 位二進制數（最高位為 1），統計這些數中 1 的總個數。

規律發現

以 m=4 為例，數字範圍 1000~1111。去掉固定的最高位 1，剩下 3 位自由變化，共 2^3 = 8 個數。這 3 位中 0 和 1 出現次數相等，各佔總位數的一半。

總位數 = (m-1) * 2^(m-1)，其中 1 的個數 = (m-1) * 2^(m-2)。加上最高位固定的 2^(m-1) 個 1，得：

ans = 2^(m-1) + (m-1) * 2^(m-2)

AC 代碼

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    while (n--) {
        int m;
        cin >> m;
        long long ans = pow(2, m-1) + (m-1) * pow(2, m-2);
        cout << ans << '\n';
    }
    return 0;
}

注意

• m ≤ 30，long long 足夠。
• 可用位運算 1LL << (m-1) 替代 pow 避免浮點誤差。