本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ1002
正解：矩阵树定理+高精度
解题报告：
推一推式子，发现一个很显然的递推式：$f[n]=f[n-1]*3-f[n-2]+2$，然后就是高精度辣！
昨晚离开机房前5分钟写完的，我好棒棒哦...
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 150;
const int mod = 100000000;
int n;
struct num{
int a[1000],len;
inline void print(){
printf("%d",a[len]);
for(int i=len-1;i>=1;i--) printf("%08d",a[i]);
}
}f[MAXN],b,c,d;
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline num cheng(num tmp,int nn){
c.len=tmp.len;
for(int i=1;i<=tmp.len;i++) c.a[i]=tmp.a[i]*nn;
for(int i=1;i<=tmp.len;i++) c.a[i+1]+=c.a[i]/mod,c.a[i]%=mod;
while(c.a[ c.len+1 ]>0) c.len++,c.a[ c.len+1 ]+=c.a[ c.len ]/mod,c.a[ c.len ]%=mod;
return c;
}
inline num jian(num tmp,num tmp2){
c.len=max(tmp.len,tmp2.len); for(int i=1;i<=c.len+2;i++) c.a[i]=0;
for(int i=1;i<=c.len;i++) c.a[i]=tmp.a[i]-tmp2.a[i];
for(int i=1;i<=c.len;i++) if(c.a[i]<0) c.a[i+1]--,c.a[i]+=mod;
while(c.a[c.len]==0) c.len--;
return c;
}
inline num jia(num tmp,num tmp2){
c.len=max(tmp.len,tmp2.len); for(int i=1;i<=c.len+2;i++) c.a[i]=0;
for(int i=1;i<=c.len;i++) c.a[i]=tmp.a[i]+tmp2.a[i];
for(int i=1;i<=c.len;i++) c.a[i+1]+=c.a[i]/mod,c.a[i]%=mod;
while(c.a[ c.len+1 ]>0) c.len++,c.a[ c.len+1 ]+=c.a[ c.len ]/mod,c.a[ c.len ]%=mod;
return c;
}
inline void work(){
n=getint(); f[1].len=f[2].len=1; f[1].a[1]=1; f[2].a[1]=5;
d.len=1; d.a[1]=2;
for(int i=3;i<=n;i++) {
b=cheng(f[i-1],3);
f[i]=jian(b,f[i-2]);
f[i]=jia(f[i],d);
}
f[n].print();
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。