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
Daily Recommendation
views 4