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;

}