首页 > 试题广场 >

勘测

[编程题]勘测

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

备注:

数据范围：
对于100%的数据保证 n ≤ 5×10⁶

算法知识视频讲解

憕

发表于 2022-11-08 21:46:37

H-游戏矩阵快速幂考点是邻接矩阵的n次方的意义考虑矩阵乘法的定义：令 C=A×B C=A×B Cij=∑k=1nAik×Bkj Cij=∑k=1nAik×Bkj 那么 A2ij=∑k=1nAik×Akj Aij2=∑k=1nAik×Akj 邻接矩阵A中的元素都是用0,1来表示是否联通的，或者展开全文