题目大意：（略）
题解：
第一眼，这不是矩阵树裸体，看了看样例，心想3就有16，那100岂不是要上天……
果然炸long long……emmmm该不会要打高精除吧……害怕，按照老师的话，不可能考高精除（++flag）……一定有鬼！
果然vfk的题解教育了我……
大力化简行列式……emmmmm害怕。
得出一个神奇的递推式$Ans_{[i]}=3*Ans_{[i-1]}-Ans_{[i-2]}+2,Ans_{[1]}=1,Ans_{[2]}=5$。
不如打表……
代码：
1 #include "bits/stdc++.h" 2 3 using namespace std; 4 5 typedef long long ll; 6 7 const int N=50; 8 9 struct Bigint{ 10 11 inline void e(int k){ 12 memset(a,0,sizeof(a)); 13 if(!k) {w=1,a[1]=0;return;} 14 w=0; 15 while(k) a[++w]=k%10,k/=10; 16 } 17 int a[N],w; 18 inline void update(){ 19 for(int i=1;i<=w;++i) 20 a[i+1]+=a[i]/10,a[i]%=10; 21 while(a[w+1]) 22 ++w,a[w+1]+=a[w]/10,a[w]%=10; 23 } 24 friend Bigint operator +(Bigint a,Bigint b){ 25 Bigint c;c.e(0); 26 for(int i=1;i<=a.w||i<=b.w;++i) 27 c.a[i]=a.a[i]+b.a[i]; 28 c.w=max(a.w,b.w); 29 c.update(); 30 return c; 31 } 32 friend Bigint operator -(Bigint a,Bigint b){ 33 for(int i=1;i<=a.w;++i){ 34 a.a[i]-=b.a[i]; 35 if(a.a[i]<0) a.a[i+1]-=1,a.a[i]+=10; 36 } 37 while(!a.a[a.w]) --a.w; 38 return a; 39 } 40 friend Bigint operator *(Bigint a,int b){ 41 for(int i=1;i<=a.w;++i) 42 a.a[i]*=b; 43 a.update(); 44 return a; 45 } 46 inline void output(){ 47 for(int i=w;i;--i) 48 putchar(a[i]+'0'); 49 putchar(' '); 50 } 51 }ans[105]; 52 53 int main(){ 54 ans[1].e(1),ans[2].e(5); 55 ans[0].e(2); 56 int n; 57 scanf("%d",&n); 58 for(int i=3;i<=n;++i) 59 ans[i]=ans[i-1]*3-ans[i-2]+ans[0]; 60 ans[n].output(); 61 }