列表

详情


NC212957. 杂技演员

描述

有一群杂技演员,他们会彼此踩在对方的背上表演杂技。
在A、B、C一共三个舞台上,有n个胖瘦不同的杂技演员,从胖到瘦依次按从下到上的顺序彼此堆叠着在舞台A上表演杂技,他们将借助舞台C,表演将所有演员移动到B舞台上的浮夸操作。
移动有以下规则:
1.每次只能移动一个演员,在移动操作的之前和之后,他必须在舞台的最上方,换句话说,在移动操作的之前和之后,他的背上不能站人。
2.任何时刻不能有一个演员站在一个比他瘦的人的上方,否则这样会把队友踩死(太残忍了~)。

请问需要移动多少步才能将所有演员移动到B舞台上?
答案可能很大,请对1e9+7取模

输入描述

输入一行一个数n,表示有多少个杂技演员
(1<=n<=1e18)

输出描述

需要移动的步数(对1e9+7取模)

示例1

输入:

1

输出:

1

说明:

直接将一个杂技演员移动到B轴

原站题解

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

C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-12-29 20:43:07

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin >> n;
	long long ans=1,m=1000000007;
	long long a=2;
	while (n>0){
		if (n%2==1) ans=ans*a%m;
		a=a*a%m;
		n/=2;
	}
	cout << ans-1;
}

Python3 解法, 执行用时: 41ms, 内存消耗: 4608K, 提交时间: 2022-06-08 12:45:38

print((pow(2,int(input()),1000000007)-1)%1000000007)

上一题