TopCoder Statistics - Problem Statement

Problem Statement

The Fibonacci sequence is defined as follows:

F[0] = 0
F[1] = 1
for each i >= 2: F[i] = F[i-1] + F[i-2]

Thus, the Fibonacci sequence starts as follows: 0, 1, 1, 2, 3, 5, 8, 13, ... The elements of the Fibonacci sequence are called Fibonacci numbers.

Fibonacci base is a positional numeral system. The only two allowed digits are 0 and 1. The weights assigned to positions in the number are all distinct positive Fibonacci numbers, in order. For example, in Fibonacci base the sequence of digits 1101 represents the number 1*5 + 1*3 + 0*2 + 1*1 = 9. Some numbers have more than one representation in Fibonacci base. For example, we can also represent 9 as 10001, because 1*8 + 0*5 + 0*3 + 0*2 + 1*1 = 9.

Consider the following greedy algorithm:

decompose(n):
    L = an empty list
    while n &gt; 0:
        find the largest Fibonacci number f &lt;= n
        append f to L
        n = n-f
    return L

It can easily be shown that the above algorithm will write any positive integer n as a sum of distinct Fibonacci numbers. In other words, the above algorithm chooses one particular representation of n in Fibonacci base. For example, for n=9 we get the representation 10001 (i.e., 8+1), and for n=30 we get 1010001 (i.e., 21+8+1).

We can now define a new function g. The value g(n) is computed as follows:

Use the above algorithm to find a representation of n in Fibonacci base.
Take the sequence of digits obtained in step 1, and interpret it as a binary number (i.e., a number in base 2).
Return the value of that binary number.

For example, suppose that n=30. First, we compute that 30 in Fibonacci base is 1010001. Next, we compute that 1010001 in base 2 is 64+16+1=81. Hence, g(30)=81.

You are given longs A and B. Compute and return the following value: (g(A) xor g(A+1) xor g(A+2) xor ... xor g(B-2) xor g(B-1) xor g(B)) modulo 1,000,000,007.

Definition

Class:: FibonacciXor
Method:: find
Parameters:: long, long
Returns:: int
Method signature:: int find(long A, long B)
(be sure your method is public)

Constraints

B will be between 1 and 10^15, inclusive.
A will be between 1 and B, inclusive.

Examples

1

2

Returns: 3

We have g(1)=1, g(2)=2, and (1 xor 2)=3.
3

10

Returns: 25

Our greedy algorithm chooses the following Fibonacci base representations for the numbers 3 through 10: 00100 00101 01000 01001 01010 10000 10001 10010 (Note that for clarity we included some leading zeros in some of the representations.) If we consider these as base-2 numbers, their values are 4, 5, 8, 9, 10, 16, 17, and 18. Thus, the answer is (4 xor 5 xor 8 xor ... xor 18) = 25.
1

1000000000000000

Returns: 780431495

Don't forget the modulo 1,000,000,007.
2

100

Returns: 157
1

1

Returns: 1
2

999999999999999

Returns: 17385925
10

100

Returns: 148
100

1000

Returns: 13416
1000

10000

Returns: 119314
22

222222222

Returns: 476633145
303783

839857170365055

Returns: 860153235
537770

575705943831061

Returns: 501014543
312830

509727412966604

Returns: 750373920
139651

575355986365932

Returns: 808237869
536398

578821493810863

Returns: 257291661
109456

362105918818764

Returns: 300855333
288013

333407259098588

Returns: 536515565
63589

738029935493550

Returns: 960254407
209059

610447807562123

Returns: 728281549
134083

702878014889867

Returns: 367638187
262972

821890082379147

Returns: 357946731
256794

921935621429090

Returns: 167941069
129551

191606310548596

Returns: 81496442
235640

336776559653448

Returns: 540565166
96570

115566612458516

Returns: 291784704
737523

833360156467271

Returns: 682328844
267217

270070644966607

Returns: 54716826
67935

76125811613182

Returns: 68756598
258117

323257586407755

Returns: 452274446
744673

749342521984668

Returns: 799222469
999999999991341

1000000000000000

Returns: 855583
1

999999999278548

Returns: 526764859
11009325

999999999741233

Returns: 329969964
56812273

999999999999991

Returns: 204958443
999999915663557

999999999999997

Returns: 55583203
999999999999999

1000000000000000

Returns: 6
836602710

999999999999974

Returns: 258454132
189396

999999999999747

Returns: 32041677
136

999999999888609

Returns: 21768373
999999999999953

999999999999982

Returns: 208
2

999999999999838

Returns: 780430525
1

999999999999876

Returns: 780430460
1

999999946660279

Returns: 936732274
3066778

3365700

Returns: 459926201
999999985762577

999999999998973

Returns: 595997730
3266

999999999999970

Returns: 780464519
64

999999994923890

Returns: 600523003
13273

513501116

Returns: 270327387
1

999999999981510

Returns: 774506189
90829

999999999999932

Returns: 773770674
155869

312830

Returns: 51226192
999999981092971

999999999999996

Returns: 587856795
346478648

999999999999926

Returns: 585770998
4

999999999997597

Returns: 17348372
27

999999999999963

Returns: 17385528
154

345803467

Returns: 591494449
795848

693864222

Returns: 368272327
999999999999984

1000000000000000

Returns: 379573015
93089

659183525

Returns: 604769580
1185

64198415

Returns: 398071992
192

43954415

Returns: 973550040
1

1114606616

Returns: 17094438
1

999999999941989

Returns: 15275640
245342055

999999994870661

Returns: 420946694
384

371684638

Returns: 726664424
6733390

999999999971929

Returns: 257745539
363012

999999562529243

Returns: 795931964
13321

999999999997779

Returns: 18178304
4872

999999987727149

Returns: 1217398
999999080775991

999999999938143

Returns: 631607285
26

389

Returns: 5337
4266612

999999977086571

Returns: 780852956
5804

999999999999919

Returns: 17552972
79973

320507341

Returns: 677568665
1317779

1525675206

Returns: 151001523
167

999999999902728

Returns: 761398979
2668387

1000000000000000

Returns: 128202881
35188

32564777

Returns: 474636376
131

1008730

Returns: 424425033
999999999965780

999999999993551

Returns: 3904578
498454011879264

806515533049393

Returns: 991479653
3275839243

956845458654523

Returns: 720969305

Statistics

Problem Statement for "FibonacciXor"

Problem Statement

Definition

Constraints

Examples