勘测

NC19840. 勘测

描述

Actci偶然发现了一个矿洞，这个矿洞的结构类似与一棵二叉树，Actci发现的矿洞恰好位于根节点处，为了尽快挖掘，Actci找来了她的小伙伴们来帮忙，由于地质原因，每天小伙伴们只能打通到一条到子节点的道路(不消耗时间)，也就是说每天一个节点只能向一个子节点建设道路，走一条路需要一天的时间，当发现一条道路后，会有一部分小伙伴选择留下来继续勘测，假设小伙伴们有无数个，树的深度足够大，问第n天最多共建设几条道路。

输入描述

一行，一个数n。

输出描述

一行，一个数表示最多建设的道路数，答案对 10000000007 取模。

示例1

输入:

输出:

说明:

样例解释：
设n号点的子节点编号为n×2和n×2+1，根节点编号为1.
第一天1->2,在1，2处留有一部分人，道路数为1。
第二天1->3,2->4,在2,3,4处留有人，道路数为3.

示例2

输入:

输出:

6531708670

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 218ms, 内存消耗: 376K, 提交时间: 2019-04-23 21:47:40

#include<stdio.h>
int main()
{
	long long n,a=1,b=1,c,d=1,k=10000000007;
	scanf("%lld",&n);
	int i;
	for(i=2;i<=n;i++)
	{
		d=d+a+b;
		d=d%k;
		a=a%k;
		b=b%k;
		c=a;
		a=a+b;
		b=c;
	}
	printf("%lld",d);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 39416K, 提交时间: 2020-02-14 23:27:53

#include<iostream>
using namespace std;
long long a[5000005];
int main()
{
	long long int c=10000000007,b;
	cin>>b;
	a[1]=1,a[2]=3;
	for(int i=3;i<=b;i++)
	a[i]=(a[i-1]+a[i-2]+2)%c;
	cout<<a[b]<<endl;
}

Python3(3.5.2) 解法, 执行用时: 1490ms, 内存消耗: 3560K, 提交时间: 2018-12-22 21:22:41

a = 0
b = 1


n = int(input())
for i in range(n-1):
    sum = (a + b + 2) % 10000000007
    a = b
    b = sum

print(b)