F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2660. -- [Beijing wc2012]最多的方案

2660: [Beijing wc2012]最多的方案

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 760  Solved: 446
[Submit][Status][Discuss]

Description

       第二关和很出名的斐波那契数列有关,地球上的OIer都知道:F1=1, F2=2, Fi = Fi-1 + Fi-2,每一项都可以称为斐波那契数。现在给一个正整数N,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数,那么对一个N最多可以写出多少种方案呢?

Input

       只有一个整数N

Output

       一个方案数

Sample Input

16

Sample Output

4

HINT



Hint:16=3+13=3+5+8=1+2+13=1+2+5+8

对于30%的数据,n<=256

对于100%的数据,n<=10^18

Source

[Submit][Status][Discuss]

HOME Back