YetAnotherHanoiProblem

There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ $10^5$ ), indicating the number of test cases. For each test case:
Each line contains one integer n (1 ≤ n ≤ $10^6$ ), indicating the total number of discs.

C++14(g++5.4) 解法, 执行用时: 163ms, 内存消耗: 9232K, 提交时间: 2020-09-18 13:23:47

#include <bits/stdc++.h>
using namespace std;
long long sz[1000010];
int main()
{
	int a;
	cin>>a;
	sz[0]=0;
	for(int i=1;i<=1000005;i++)
	{
		sz[i]=((sz[i-1]+1)*3-1)%1000000007;
	}
	while(a--)
	{
		long long k;
		cin>>k;
		cout<<sz[k]<<endl;
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 55ms, 内存消耗: 9324K, 提交时间: 2020-06-03 16:54:00

#include<cstdio>
long long int a[1000005];
int main()
{
	a[0]=1;
	for(int i=1;i<1000005;i++)
	{
		a[i]=a[i-1]*3;
		a[i]=a[i]%(1000000000+7);
	}
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		printf("%d\n",a[n]-1);
	}
}

pypy3(pypy3.6.1) 解法, 执行用时: 1236ms, 内存消耗: 31076K, 提交时间: 2020-06-03 16:06:20

mod = 1_000_000_007
for _ in range(int(input())):
    print((pow(3, int(input()), mod) - 1 + mod) % mod)

Python3(3.5.2) 解法, 执行用时: 1908ms, 内存消耗: 4344K, 提交时间: 2020-07-07 19:46:42

n=eval(input())
for i in range(n):
    t=eval(input())
    print(pow(3, t,1000000007)-1)

详情