CSES Counting Bits 題解

題目

題目見網址：https://cses.fi/problemset/task/1146/
我懶得複製過來了XD
簡單來說就是輸入 $n$，要問 $1$ 到 $n$ 中的所有正整數寫成二進位之後總共有幾個 $1$。
其實這是排列組合那邊的經典問題，只是數學課我們是直接在十進位算。

解法

憶起高中數學

回想一下高中排列組合的某個問題：

$1$~$999$ 中共有多少個 $9$？

有兩種解法，一種是分別算個位數、十位數、百位數有多少 $9$，但有另一種比較快的看法(機率觀點)：
我們要找的相當於

$$000, 001, 002, 003, \dots, 999$$

中 $1$ 的個數，裡面總共有 $3\times1000=3000$ 個「$0$~$9$ 的數字」，而 $0$~$9$ 出現機率相同，所以所求即為

$$3000\times\frac{1}{10}=300$$

細說本題

接著就只是十進位轉成二進位而已，我們採取的策略是先找出 $2^k - 1 \leq n$ 的最大的 $k$，然後 $1$ ~ $2^k - 1$ 中 $1$ 的數量就是 $k\times2^k\times\frac12$。剩下再考慮 $2^k$ ~ $n$ 有多少數字 $1$ 即可。
這樣能快速地把大量數字算完。接著，所以 $2^k$ ~ $n$ 中每個數字的(二進位表示)最高位都是 $1$，而且最高位是第 $k+1$ 位，總共有 $n-2^k+1$ 個 $1$。再來我們將這幾個數字最高位的 $1$ 都拔掉，我們要再計算剩下的 $1$ 總共有多少。

在繼續說明之前，我們先舉個例子比較清楚，以 $n=14=1110_2$ 為例：
第一步驟解決掉 $1$ ~ $7$，共有 $3\times 2^3\times\frac12=12$ 個 $1$
接著我們要找出 $1000_2, 1001_2, 1010_2, 1011_2, 1100_2, 1101_2, 1110_2$ 中所有 $1$ 的數量
首先最高位的 $1$ 有 $14-8+1=7$ 個，將這些首位的 $1$ 拔掉，上面那 $7$ 個數字變成
$000_2, 001_2, 010_2, 011_2, 100_2, 101_2, 110_2$
有沒有發現！這不是一樣的問題嗎？找出 $1$ ~ $110_2$ (也就是 $6$) 中 $1$ 的數量！

所以我們可以用上遞迴！不過有遞迴就要有 base case，不難想到這裡的 base case 就是 $n=0$ 時，回傳 $0$

程式碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll counting_bits(ll n){
    if (n == 0) return 0; // base case
    int k = __lg(n);
    ll count = 0;
    ll m = 1LL << k; // 記得要 1LL 啊！我第一次送的時候漏掉這個所以錯了
    count += 1LL * k * (m >> 1);
    count += n - m + 1;
    count += counting_bits(n - m); // n - m 是把最高位拔掉，列個二進位的直式減法就顯然了
    return count;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    ll n;
    cin >> n;
    cout << counting_bits(n);
}

笑死 CTF 解太多，文章結尾都很想來個「所以 Flag 就是……」