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][2]{}; dp[0][0]=1;
  30.         for(int j=1; j<=n; j++){
  31.             for(int k=1; k<=i; k++){
  32.                 if(((1ll<<k)-1)<=j){
  33.                     if(k==i) {
  34.                         dp[j][1]+=dp[j-((1ll<<k)-1)][0];
  35.                         dp[j][1]%=M;
  36.  
  37.                         dp[j][1]+=dp[j-((1ll<<k)-1)][1];
  38.                         dp[j][1]%=M;
  39.                     }
  40.                     else{
  41.                         dp[j][0]+=dp[j-((1ll<<k)-1)][0];
  42.                         dp[j][0]%=M;
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.         ans+=dp[n][1];
  48.     }
  49.     cout<<ans<<endl;
  50. }
  51.  
  52. int32_t main() {
  53.     fast;
  54.  
  55.     int t;
  56.     t=1;
  57.     // cin>>t;
  58.     while(t--){
  59.         solve();
  60.     }
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
1273079863
https://ideone.com/395s63
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!