题目大意:(略)
题解:
第一眼,这不是矩阵树裸体,看了看样例,心想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$。
不如打表……
代码:
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int N=; struct Bigint{ inline void e(int k){
memset(a,,sizeof(a));
if(!k) {w=,a[]=;return;}
w=;
while(k) a[++w]=k%,k/=;
}
int a[N],w;
inline void update(){
for(int i=;i<=w;++i)
a[i+]+=a[i]/,a[i]%=;
while(a[w+])
++w,a[w+]+=a[w]/,a[w]%=;
}
friend Bigint operator +(Bigint a,Bigint b){
Bigint c;c.e();
for(int i=;i<=a.w||i<=b.w;++i)
c.a[i]=a.a[i]+b.a[i];
c.w=max(a.w,b.w);
c.update();
return c;
}
friend Bigint operator -(Bigint a,Bigint b){
for(int i=;i<=a.w;++i){
a.a[i]-=b.a[i];
if(a.a[i]<) a.a[i+]-=,a.a[i]+=;
}
while(!a.a[a.w]) --a.w;
return a;
}
friend Bigint operator *(Bigint a,int b){
for(int i=;i<=a.w;++i)
a.a[i]*=b;
a.update();
return a;
}
inline void output(){
for(int i=w;i;--i)
putchar(a[i]+'');
putchar('\n');
}
}ans[]; int main(){
ans[].e(),ans[].e();
ans[].e();
int n;
scanf("%d",&n);
for(int i=;i<=n;++i)
ans[i]=ans[i-]*-ans[i-]+ans[];
ans[n].output();
}