福州网站设计费用,中山网络推广,中国建设银行信用卡中心网站,岳阳建设银行网站题干#xff1a;
Actci偶然发现了一个矿洞#xff0c;这个矿洞的结构类似与一棵二叉树#xff0c;Actci发现的矿洞恰好位于根节点处#xff0c;为了尽快挖掘#xff0c;Actci找来了她的小伙伴们来帮忙#xff0c;由于地质原因#xff0c;每天小伙伴们只能打通到一条到子…题干
Actci偶然发现了一个矿洞这个矿洞的结构类似与一棵二叉树Actci发现的矿洞恰好位于根节点处为了尽快挖掘Actci找来了她的小伙伴们来帮忙由于地质原因每天小伙伴们只能打通到一条到子节点的道路(不消耗时间)也就是说每天一个节点只能向一个子节点建设道路走一条路需要一天的时间当发现一条道路后会有一部分小伙伴选择留下来继续勘测假设小伙伴们有无数个树的深度足够大问第n天最多共建设几条道路。
输入描述:
一行一个数n。
输出描述:
一行一个数表示最多建设的道路数答案对 10000000007 取模。
示例1
输入
复制
2
输出
复制
3
说明
样例解释
设n号点的子节点编号为n×2和n×21根节点编号为1.
第一天1-2,在12处留有一部分人道路数为1。
第二天1-3,2-4,在2,3,4处留有人道路数为3.
示例2
输入
复制
100
输出
复制
6531708670
备注:
数据范围
对于100%的数据保证 n ≤ 5×106 解题报告 模拟出前几项打表发现是个fib数列有关。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 5e6 5;
ll mod 10000000007;
ll f[MAX];
int main()
{int n;cinn;f[1]1;for(int i 2; in10; i) {f[i]f[i-1]f[i-2];f[i]%mod;}printf(%lld\n,(f[n3]mod-2)%mod);return 0 ;}
