#D. [CZOI2023 D] 数学作业

    传统题 1000ms 256MiB

[CZOI2023 D] 数学作业

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

今天小 X 的数学老师带领大家学习了斐波那契序列:

斐波那契序列指的是这样一个数列:{1,2,3,5,8,13,21,34}\{1,2,3,5,8,13,21,34\}。从第 33 个数开始,每个数都是前两个数的和,比如 8=3+5,34=13+218=3+5,34=13+21。数列里的数叫做斐波那契数。

一个数 nn 的斐波那契表示是指把 nn 写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如 1414 有三种斐波那契表示:14=1+13,14=1+5+8,14=1+2+3+814=1+13,14=1+5+8,14=1+2+3+8。数学老师给小 X 留下了一个数学作业,她告诉小 X 一个正整数 nn,想让小 X 算出 nn 有多少种不同的斐波那契表示。

小 X 请你帮助他完成他的数学作业。

输入格式

第一行为一个正整数 nn

输出格式

输出一行一个整数表示答案。

14
3
1110
21
1000000000000
283392

数据范围

对于测试点 151\sim 51n1041\leq n\leq 10^4

对于测试点 686\sim 81n1091\leq n\leq 10^9

对于测试点 9109\sim 101n10121\leq n\leq 10^{12}

[CZR-000-VP] 常州市程序设计小能手 2023

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-5-27 13:00
结束于
2023-5-27 17:00
持续时间
4 小时
主持人
参赛人数
42