fork download
copy 
  1. //Jagsxi
  2. //This is a code trying to explain the above tutorial. Please try to code it yourself for better understanding.Submitting this will not get you AC. :)
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. const int MOD = 1000000007;
  6.  
  7. vector<long> allfib;
  8. int fibn;
  9.  
  10. vector<int> getLetty(long x)
  11. {
  12.     // get the Letty representation of x
  13.     vector<int> res(fibn);
  14.     for (int i = fibn - 1; i >= 0; i--) {
  15.         if (x >= allfib[i]) {
  16.             res[i] = 1;
  17.             x -= allfib[i];
  18.         }
  19.     }
  20.     return res;
  21. }
  22.  
  23. vector<int> getXorFirst(long x) // get the  Fibonacci xor of 0, 1, ... x.
  24. { 
  25.  
  26.     vector<int> X = getLetty(x);
  27.     vector<int> res(fibn);
  28.  
  29.     for (int i = 0; i < fibn; i++) { // for each bit position i
  30.         // is the number of fibonacci numbers <= X with 1 in the i-th
  31.         // position an odd number or not?
  32.         int dp[fibn + 1][2][2];
  33.         // solve function f(j, less, last):
  34.         // j : We have assigned all positions greater than or equal to i
  35.         // less: The chosen number is already less than X
  36.         // base case j = 0
  37.         for (int less = 0; less < 2; less++) {
  38.             for (int last = 0; last < 2; last++) {
  39.                 dp[0][less][last] = 1;
  40.             }
  41.         }
  42.  
  43.         for (int j = 1; j <= fibn; j++) {
  44.             for (int less = 0; less < 2; less++) {
  45.                 for (int last = 0; last < 2; last++) {
  46.                     dp[j][less][last] = 0;
  47.                     // decide position j - 1
  48.                     int mx;
  49.                     if ( (last == 1) || ( !less && (X[j-1] == 0) ) ) {
  50.                         mx = 0;
  51.                     } else {
  52.                         mx = 1;
  53.                     }
  54.                     for (int v = 0; v <= mx; v++) {
  55.                         if ( (j-1 != i) || (1 == v) ) {
  56.                             // we can
  57.                             int newless = (less || (v < X[j-1]) );
  58.                             dp[j][less][last] ^= dp[j-1][newless][v];
  59.                         }
  60.                     }
  61.                 }
  62.             }
  63.         }
  64.         //base cases, j = -1, j = -2
  65.         res[i] = dp[fibn][0][0];
  66.     }
  67.     return res;
  68.  
  69. }
  70.  
  71. void makeFibonacci(long T)
  72. {
  73.     long a = 1, b = 2;
  74.     while (a <= T) {
  75.         allfib.push_back(a);
  76.         long c = a + b;
  77.         a = b;
  78.         b = c;
  79.     }
  80.     fibn = allfib.size();
  81.     //cout << fibn <<endl;
  82.     //cout << allfib[fibn-1] << " is the " << (fibn-1)<<"-th"<<" fibonacci"<<endl;
  83. }
  84.  
  85.  
  86. int find(long A, long B)
  87. {
  88.     makeFibonacci(max(A,B));
  89.  
  90.     vector<int> sb = getXorFirst(B);
  91.     vector<int> sa = getXorFirst(A - 1);
  92.     int res = 0;
  93.     for (int i = fibn - 1; i >= 0; i--) {
  94.         res = (2*res) % MOD;
  95.         if (sb[i] != sa[i]) {
  96.             res++; 
  97.         }
  98.     }
  99.     return (int)(res % MOD);
  100. }
  101. int main()
  102. {
  103. int t;
  104. cin>>t;
  105. while(t--)
  106. {
  107. long A,B;
  108. cin>>A>>B;
  109. allfib.clear();
  110.  makeFibonacci(max(A,B));
  111.  
  112.     vector<int> sb = getXorFirst(B);
  113.     vector<int> sa = getXorFirst(A - 1);
  114.     int res = 0;
  115.     for (int i = fibn - 1; i >= 0; i--) {
  116.         res = (2*res) % MOD;
  117.         if (sb[i] != sa[i]) {
  118.             res++; 
  119.         }
  120.     }
  121.     cout<<res%MOD<<endl;
  122. }
  123. }
  124.  
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
2
1 2
3 10
stdout
copy 
3
25
https://ideone.com/3FqA29
language:
C++ (gcc 8.3)
created:
8 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!