題目描述
輸入一個正整數m,請輸出從0到m中每一個數字二進制數中含有1的個數的總和,由于數值較大結果需要模100000.

輸入格式
一個m

輸出格式
二進制數中含有1的個數的總和s

輸入輸出樣例
輸入
2
輸出
2
輸入
5
輸出
7
說明/提示
樣例說明
20%的數據 m<=500
50%的數據 m<=1000
70%的數據 m<=50000000
100%的數據 m<=100000000

內存限制500MB

知識點：
統計kk這個數在二進制的表示下有幾個1，代碼如下：

#include <iostream> using namespace std;int main() {int kk;cin>>kk;int count = 0;while(kk){kk = kk & (kk-1);//核心代碼count++;}cout<<count<<endl;return 0; }

解題思路:
這種解法,有幾個1就執行幾次。
把一個整數減去1，再與原數字做按位與運算，會把原數二級制位中最右邊的1變成0.那么一個整數二進制表示中有幾個1，就可以進行幾次這樣的操作。
0111減去1變成0110，二者進行與運算變成0110，則把原數做右邊的1變成0.循環往復直到全為0結束。

代碼如下:

#include <iostream> using namespace std;int main() {int m;cin >> m;int count = 0;for (int i = 0; i <= m; i++) {int c = i;while (c) {c = c & (c - 1);count++;}count = count % 100000;}cout << count << endl;return 0; }

但是我們會發現，上面的代碼在運算過程，會進行很多重復運算，我們明明可以對這些數字進行記憶化，在運算過程中，之前算過的數，我們就不要算了，所以我們可以用dp

代碼如下：

#include <iostream> using namespace std; const int N = 100000010; const int MOD = 100000; int dp[N];int main() {int sum = 0;int m;cin >> m;dp[0] = 0;for (int i = 1; i <= m; i++) {dp[i] = dp[i & (i - 1)] + 1;dp[i] %= MOD;sum += dp[i];sum %= MOD;}cout << sum << endl;return 0; }

總結

以上是生活随笔為你收集整理的统计二进制数-dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。