【BZOJ1002】轮状病毒

    推了半天发现是打表找规律...基尔霍夫的证明方法看得不是很懂

    递推式：f[n]=3*f[n-1]-f[n-2]+2，初始条件f[1]=1,f[2]=5

    然后高精一下。（终于找到了一些个人比较喜欢的高精结构体打法）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;

struct BigNum
{
	int a[maxn];
	int l;
	BigNum (int _a=0) {memset(a,0,sizeof(a));a[1]=_a;l=1;}
	int &operator [] (int x) {return a[x];}
	friend BigNum operator + (const BigNum &a,const BigNum &b);
	friend BigNum operator - (const BigNum &a,const BigNum &b);
	friend BigNum operator * (const BigNum &a,const BigNum &b);
}f[maxn],a2,a3,_v;

BigNum operator + (const BigNum &a,const BigNum &b)
{
	memset(_v.a,0,sizeof(_v.a));
	_v.l=max(a.l,b.l);
	for (int i=1;i<=_v.l;i++)
	_v[i]+=a.a[i]+b.a[i],_v[i+1]+=_v[i]/10,_v[i]%=10;
	if (_v[_v.l+1]) _v.l++;
	return _v;
}

BigNum operator - (const BigNum &a,const BigNum &b)
{
	memset(_v.a,0,sizeof(_v.a));
	_v.l=a.l;
	for (int i=1;i<=_v.l;i++)
	{
		_v[i]+=a.a[i]-b.a[i];
		if (_v[i]>=0) continue;
		_v[i+1]--;
		_v[i]+=10;
	}
	while (_v.l>1 && !_v[_v.l]) _v.l--;
	return _v;
}

BigNum operator * (const BigNum &a,const BigNum &b)
{
	memset(_v.a,0,sizeof(_v.a));
	_v.l=a.l+b.l-1;
	for (int i=1;i<=a.l;i++)
	for (int j=1;j<=b.l;j++)
	_v[i+j-1]+=a.a[i]*b.a[j];
	for (int i=1;i<=_v.l;i++)
		_v[i+1]+=_v[i]/10,_v[i]%=10;
	if (_v[_v.l+1]) _v.l++;
	while (_v.l>1 && !_v[_v.l]) _v.l--;
	return _v;
}

int main()
{
	int n;
	scanf("%d",&n);
	f[1]=BigNum(1);
	f[2]=BigNum(5);
	a2=BigNum(2);
	a3=BigNum(3);
	for (int i=3;i<=n;i++) f[i]=f[i-1]*a3-f[i-2]+a2;
	for (int i=f[n].l;i;i--) printf("%d",f[n][i]);
	return 0;
}