emm……
正解：矩阵树定理，但是本宝宝不会求基尔霍夫矩阵。
开始考场方法：
手动模拟$n=1--5$时的答案（数不大，~~画画就出来了~~要画上半个小时）。
画出来，答案是这样的：$1$ $5$ $16$ $45$ $121$
然后简单根据题目出处和难度蒙了一下感觉第$n$项的答案和$n-1$,$n-2$的答案有关。
再看看增长率$(\frac{ans[n-1]}{ans[n-2]})$大概是$2--3$之间，并且比较靠近三。
于是，就想 $ans[n]$ $=$ $ans[n-1]*3$ $±$ $……$
又因为差的不是一个常数，所以
$ans[n]$ $=$ $3*ans[n-1]-ans[n-2]$ $±$ $……$
之后，惊喜的发现每个$ans[n]$ 与 $3*ans[n-1]-ans[n-2]$ 都差$2$。
最终，蒙了一个表达式：$ans[n]=$ $3*ans[n-1]-ans[n-2]+2$
看数据范围，需要高精。
之后一脸懵逼的$AC$了。
代码附上：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; //F(n)=3*F(n-1)-F(n-2)+2,F(1)=1,F(2)=5.; int ans[103][10010]; int len[103]; int mul[10010]; void pluse(int x) { int m=x-2; int n=x-1; int cnt=0;int l=len[n]; for(int i=1;i<=l;i++) { mul[i]=(ans[n][i]*3+cnt)%10; cnt=(ans[n][i]*3+cnt)/10; } if(cnt!=0) mul[++l]=cnt; cnt=2; for(int i=1;i<=l;i++) { ans[x][i]=(mul[i]-ans[m][i]+cnt+100)%10; if(mul[i]-ans[m][i]+cnt<0) cnt=-1; else cnt=(mul[i]-ans[m][i]+cnt)/10; } if(cnt!=0) ans[x][l+1]=cnt,len[x]=l+1; else len[x]=l; return ; } int n; int main() { scanf("%d",&n); ans[1][1]=1;len[1]=1; ans[2][1]=5;len[2]=1; for(int i=3;i<=n;i++) pluse(i); for(int i=len[n];i>=1;i--) printf("%d",ans[n][i]); return 0; }
