Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒
Input
第一行有1个正整数n
Output
计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
Solution
一眼就是基尔霍夫矩阵啊
但是似乎有更优秀的解法？
直接递推，递推式：\(F(i)=3F(i-1)-F(i-2)+2~~(F(1)=1,F(2)=5)\)
证明
然后写个高精度
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100+10;
int n;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
struct Bnum{
int a[MAXN],len;
inline void init(int x)
{
memset(a,0,sizeof(a));
len=0;
while(x)a[++len]=x%10,x/=10;
}
inline Bnum operator + (const Bnum &A) const {
Bnum B;
B.init(0);
B.len=max(len,A.len);
for(register int i=1;i<=B.len;++i)
{
B.a[i]+=a[i]+A.a[i];
B.a[i+1]+=B.a[i]/10;
B.a[i]%=10;
}
if(B.a[B.len+1])B.len++;
return B;
};
inline Bnum operator - (const Bnum &A) const {
Bnum B;
B.init(0);
B.len=max(len,A.len);
for(register int i=1;i<=len;++i)
{
B.a[i]+=a[i]-A.a[i];
if(B.a[i]<0)B.a[i]+=10,B.a[i+1]--;
}
while(B.len&&!B.a[B.len])B.len--;
return B;
};
inline void print()
{
for(register int i=len;i>=1;--i)write(a[i]);
puts("");
}
};
Bnum ans,las,mlas,two,tmp;
int main()
{
read(n);
if(n==1)write(1,'\n');
else if(n==2)write(5,'\n');
else
{
las.init(5);mlas.init(1);two.init(2);
for(register int i=3;i<=n;++i)ans=las+las+las-mlas+two,mlas=las,las=ans;
ans.print();
}
return 0;
}