刚刚做的HDU 2064很好找规律，

回忆一下：

b[1] = 2;

b[n] = b[n-1] *3 + 2;

可得b[n]= 3^n-1

不懂的传送门

这题题目差不多，就是放宽条件，但只允许把最大的放在最上面。

其实我看的时候没有仔细想。。。它的输入已经暴露了它的公式。因为两题差不多，所以应该也是与3的n次幂有关。计算3的10次为59049 超过了？等等/3看看！3的9次方为19683，于是大胆猜测公式为a[n]= 3^(n-1)+1，直接AC掉。

Sample Input

2

1

10

Sample Output

2

19684

 

那么如何得到那个式子呢？

把n-2个移动到C，由于允许最大的那个盘子放上面，所以n-1到B，n到B，n-2到A，n到C，n-1到c，剩下的n-2和刚才那题一样！

故得a[n] =b[n-2] *3 + 4;(注意这里是b[n-2],不是a[n-2])

带入刚才的式子得：a[n] =( 3^(n-2)-1)*3+4=3^(n-1)+1

那么递推式呢？有了通项公式，递推式也呼吁而出：

a[1] = 2;

a[n] = a[n-1] *3 -2;

好了上代码说到这了，代码好像是多余的了。。。^ ^

递推版：

#include 
    
     using namespace std;const int MAXN=64;int main(){	int T;	__int64  a[MAXN];	a[1] =2;	scanf("%d",&T);	while(T--)	{		int n;		scanf("%d",&n);		for(int i=2;i<=n;i++)			a[i] = a[i-1] *3 -2;		printf("%I64d\n",a[n]);	}}
    

直接公式：

#include 
    
     using namespace std;int main(){	int T;	scanf("%d",&T);	while(T--)	{		int n;		scanf("%d",&n);		long long x=1;		for(int i=1;i