fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. static const int K = 41;
  5.  
  6. long long n, ans;
  7. int l, r, m;
  8. long long f[K][K][2][2];
  9.  
  10. int main() {
  11.     freopen("input.txt", "rt", stdin);
  12.     freopen("output.txt", "wt", stdout);
  13.  
  14.     scanf("%I64d%d%d", &n, &l, &r);
  15.  
  16.     m = 1;
  17.  
  18.     while ((1LL << m) <= n)
  19.         m++;
  20.  
  21.     f[0][l][0][0] = f[0][l][0][1] = 1;
  22.  
  23.     for (int i = 1; i <= m; i++) {
  24.         for (int j = l; j <= r; j++) {
  25.             if (n & (1LL << (i - 1))) {
  26.                 f[i][1][0][0] += f[i - 1][j][0][1] + f[i - 1][j][1][1];
  27.                 f[i][1][0][1] += f[i - 1][j][0][0];
  28.                 f[i][1][1][0] += 0;
  29.                 f[i][1][1][1] += f[i - 1][j][1][0];
  30.             } else {
  31.                 f[i][1][0][0] += f[i - 1][j][0][1];
  32.                 f[i][1][0][1] += 0;
  33.                 f[i][1][1][0] += f[i - 1][j][1][1];
  34.                 f[i][1][1][1] += f[i - 1][j][0][0] + f[i - 1][j][1][0];
  35.             }
  36.         }
  37.  
  38.         for (int j = 2; j <= i; j++) {
  39.             if (n & (1LL << (i - 1))) {
  40.                 f[i][j][0][0] += f[i - 1][j - 1][0][0] + f[i - 1][j - 1][1][0];
  41.                 f[i][j][0][1] += f[i - 1][j - 1][0][1];
  42.                 f[i][j][1][0] += 0;
  43.                 f[i][j][1][1] += f[i - 1][j - 1][1][1];
  44.             } else {
  45.                 f[i][j][0][0] += f[i - 1][j - 1][0][0];
  46.                 f[i][j][0][1] += 0;
  47.                 f[i][j][1][0] += f[i - 1][j - 1][1][0];
  48.                 f[i][j][1][1] += f[i - 1][j - 1][0][1] + f[i - 1][j - 1][1][1];
  49.             }
  50.         }
  51.     }
  52.  
  53.     for (int i = 1; i < m; i++)
  54.         for (int j = l; j <= r; j++)
  55.             ans += f[i][j][0][1] + f[i][j][1][1];
  56.  
  57.     for (int i = l; i <= r; i++)
  58.         ans += f[m][i][0][1];
  59.  
  60.     printf("%I64d", ans);
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 3516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9bXZHA
language:
C++ (gcc 8.3)
created:
7 years 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!