Title Description
Enter a positive integer m, Please output from 0 reach m Each number in the binary contains 1 The sum of the number of , Because of the large numerical value, the results need to be modeled 100000.

Input format
One m

Output format
Binary number contains 1 The sum of the number of s

Sample input and output
input
2
output
2
input
5
output
7
explain / Tips
Example description
20% Data for m<=500
50% Data for m<=1000
70% Data for m<=50000000
100% Data for m<=100000000

Memory limit 500MB

Knowledge points :
Statistics kk How many are there in binary representation of this number 1, The code is as follows :
#include <iostream> using namespace std; int main() { int kk; cin>>kk; int
count= 0; while(kk) { kk = kk & (kk-1);// Core code count++; } cout<<count<<endl;
return 0; }
Thinking of solving problems :
This solution , There are several 1 Just a few times .
Subtract an integer 1, And then do the bitwise and operation with the original number , Will put the original number in the rightmost position 1 become 0. How many are there in the binary representation of an integer 1, You can do this several times .
0111 subtract 1 become 0110, The operation of the two becomes 0110, Then we make the original number to the right 1 become 0. Cycle until it's all done 0 end .

The code is as follows :
#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; }
But we'll find out , The above code is in operation , There's a lot of repetition , We can memorize these numbers , In the process of operation , The number calculated before , Let's not forget it , So we can use it dp

The code is as follows :
#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; }

Technology
©2019-2020 Toolsou All rights reserved,
Huawei 2021 session Hardware Engineer Logical post (FPGA) Super detailed surface !!!Vue-element-admin upgrade ui edition virtual machine VMware Download and install the most detailed tutorial !C++ Move constructor and copy constructor sound of dripping water java Backstage interview pygame Realize full screen mode and adjustable window size mysql Database setting character set configuration modification my.ini file (windows)30 What's the experience of being a junior programmer at the age of 20 C++ Multithreading programming ( Summary of common functions and parameters )python_ cherry tree