fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. // #include <bits/stdc++.h>
  4. #include <sstream>
  5. #include <list>
  6. #include <stack>
  7. #include <deque>
  8. #include <utility>
  9. #include <queue>
  10. #include <set>
  11. #include <map>
  12. #include <assert.h>
  13. #include <bitset>
  14. #include <vector>
  15. #include <cmath>
  16. #include <string>
  17. #include <algorithm>
  18. #include <iomanip>
  19. #include <ctime>
  20. #include <iterator>
  21. #include <cstdio>
  22. #include <cstring>
  23. #include <cstdlib>
  24. #include <complex>
  25.  
  26. #define f first
  27. #define s second
  28. #define ll long long
  29. #define ld long double
  30. #define pb push_back
  31. #define files1 freopen("input.txt","r",stdin)
  32. #define files2 freopen("output.txt","w",stdout)
  33. #define files files1;files2
  34. #define mp make_pair
  35. #define fast_io ios_base::sync_with_stdio(0);cin.tie(0)
  36. #define forn() for(int i=0;i<n;i++)
  37. #define vi vector<int>
  38. #define pii pair<int,int>
  39. #define endl '\n'
  40. #define fill(x) memset((x), 0, sizeof((x)))
  41.  
  42. using namespace std;
  43.  
  44. const int inf = 2e9;
  45. const double eps = 1e-9;
  46. const int maxn = 2e5 + 10, base = 1e9 + 7;
  47. const int sigm = 26;
  48. const ll llinf = 1e18;
  49.  
  50. void bad(string mes = "Impossible"){cout << mes;exit(0);}
  51.  
  52. template<typename T>
  53. string bin(T x){
  54.     string ans = "";
  55.     while (x > 0){
  56.         ans += char('0' + x % 2);
  57.         x /= 2;
  58.     }
  59.     reverse(ans.begin(), ans.end());
  60.     return ans.empty() ? "0" : ans;
  61. }
  62.  
  63. template<typename T>
  64. T dcm(string & s)
  65. {
  66.     T x = 0;
  67.     for (int i = 0; i < s.size(); i++){
  68.         x = (x * 2) + (s[i] == '1');
  69.     }
  70.     return x;
  71. }
  72.  
  73. template<typename T>
  74. T input(){
  75.     T ans = 0, m = 1;
  76.     char c = ' ';
  77.     while (c == ' ' || c == '\n')
  78.         c = getchar();
  79.     if (c == '-')
  80.         m = -1, c = getchar();
  81.     while (c >= '0' && c <= '9'){
  82.         ans = ans * 10 + int(c - '0'), c = getchar();
  83.     }
  84.     return ans * m;
  85. }
  86.  
  87. template<typename T>
  88. T binpow(T n, T s)
  89. {
  90.     if (s == 0)
  91.         return 1LL;
  92.     if (s % 2 == 0){
  93.         T b = binpow(n, s / 2);
  94.         return ( 1LL * b * b );
  95.     } else {
  96.         return (1LL* binpow(n, s - 1) * n);
  97.     }
  98. }
  99.  
  100. ll dp[64][64][2]; // the last digit in pattern -> pattern % 2
  101.  
  102. ll realPat[64];
  103.  
  104. int main()
  105. {
  106.     ll n;
  107.     cin >> n;
  108.  
  109.     int len = bin(n).size();
  110.  
  111.     if (n == 1)
  112.         bad("1");
  113.  
  114.     dp[len - 1][1][1] = 1; // dp[len][pattern][prefix]
  115.  
  116.     for (int byte = len - 1; byte > 0; byte--){
  117.         int curLet = (((ll)n & (1LL << (byte - 1))) != 0);
  118.         for (int pattern = 1; pattern < 62; pattern++){
  119.             int inThePattern = pattern % 2;
  120.  
  121.             for (int lowerNew = 0; lowerNew < 2; lowerNew++){
  122.                 int weAreGoing = pattern + (lowerNew != inThePattern);
  123.  
  124.                 if (weAreGoing >= 62)
  125.                     continue;
  126.                 dp[byte - 1][weAreGoing][0] = (dp[byte - 1][weAreGoing][0] + dp[byte][pattern][0]) % base;
  127.  
  128.                 if (lowerNew < curLet)
  129.                 dp[byte - 1][weAreGoing][0] = (dp[byte - 1][weAreGoing][0] + dp[byte][pattern][1]) % base;
  130.  
  131.                 if (lowerNew == curLet)
  132.                 dp[byte - 1][weAreGoing][1] = (dp[byte - 1][weAreGoing][1] + dp[byte][pattern][1]) % base;
  133.             }      
  134.         }
  135.     }
  136.  
  137.     realPat[1] = 1;
  138.  
  139.     for (int i = 2; i < 62; i++){
  140.         realPat[i] = (realPat[i - 1] * 2LL + (i % 2LL)) % base;
  141.     }
  142.  
  143.     ll ans = 0;
  144.     for (int i = 1; i < 62; i++){
  145.         ans = (ans + (dp[0][i][0] * realPat[i]) % base) % base;
  146.         ans = (ans + (dp[0][i][1] * realPat[i]) % base) % base;
  147.     }
  148.  
  149.     fill(dp);
  150.     len--;
  151.     dp[len - 1][1][0] = 1;
  152.  
  153.     //ans for all lens 0..len - 1
  154.  
  155.     for (int byte = len - 1; byte >= 0; byte--){
  156.         for (int pattern = 1; pattern < 62; pattern++){
  157.             int inThePattern = pattern % 2;
  158.             ans = (ans + (dp[byte][pattern][0] * realPat[pattern]) % base) % base;
  159.  
  160.             if (byte){
  161.                 for (int lowerNew = 0; lowerNew < 2; lowerNew++){
  162.                     int weAreGoing = pattern + (lowerNew != inThePattern);
  163.                     if (weAreGoing >= 62)
  164.                         continue;
  165.                     dp[byte - 1][weAreGoing][0] = (dp[byte - 1][weAreGoing][0] + dp[byte][pattern][0]) % base;
  166.                 }      
  167.             }
  168.         }
  169.     }
  170.  
  171.     cout << ans;
  172.     return 0;
  173. }
Success #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
10
stdout
copy 
31
https://ideone.com/jhjXVe
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!