fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define pb push_back
  6. #define int long long
  7. #define f first
  8. #define s second
  9. #define pq priority_queue
  10. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  11. #define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  12.  
  13. using namespace std;
  14.  
  15. // #include <ext/pb_ds/assoc_container.hpp>
  16. // #include <ext/pb_ds/tree_policy.hpp>
  17. // using namespace __gnu_pbds;
  18.  
  19. // template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  20. // template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  21.  
  22. const ll M=1e9+7;
  23.  
  24. void solve(){
  25.     int n; cin>>n;
  26.     int lg=__lg(n)+2;
  27.     int ans=0;
  28.     for(int i=1; i<=lg; i++){
  29.         int dp[n+1]{};
  30.         dp[0]=1;
  31.         for(int k=1; k<i; k++){
  32.             for(int j=1; j<=n; j++){
  33.                 if(((1ll<<(k))-1)<=j){
  34.                     dp[j]+=dp[j-((1ll<<(k))-1)];
  35.                     dp[j]%=M;
  36.                 }
  37.             }
  38.         }
  39.         for(int j=1; j<=n; j++){ // cnt of  first value
  40.             if(n-j*((1ll<<(i))-1)<0) break;
  41.             ans+=dp[n-j*((1ll<<(i))-1)];
  42.         }
  43.     }
  44.     cout<<ans<<endl;
  45. }
  46.  
  47. int32_t main() {
  48.     #ifndef ONLINE_JUDGE
  49.         read_file;
  50.     #endif
  51.  
  52.     fast;
  53.  
  54.     int t;
  55.     t=1;
  56.     // cin>>t;
  57.     while(t--){
  58.         solve();
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
1496143
https://ideone.com/KmCb2J
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!