- 2021-03-15 00:03
*views 3*- dp
- Base conversion
- Algorithm notes
- C++
- dynamic programming
- Blue Bridge Cup training
- algorithm

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

- Java423 articles
- Python236 articles
- Vue127 articles
- Linux119 articles
- MySQL100 articles
- javascript76 articles
- SpringBoot72 articles
- C++68 articles
- more...

Daily Recommendation

views 4

views 3

©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