记录编号	197559	评测结果	AAAAAAAAAA
题目名称	[FJOI 2007] 轮状病毒	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-10-24 07:50:34	内存使用	0.33 MiB

#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>
#include<cstring>

using namespace std;

int n;

struct BigNum{
	int s[100];BigNum(){clr();return;}
	inline void clr(){memset(s,0,sizeof(s));return;}
	inline void set(int p){while(p)s[++s[0]]=p%10,p/=10;return;}
	inline void print(){for(int i=s[0];i>0;i--)printf("%d",s[i]);}
	friend BigNum operator * (BigNum temp_a,BigNum temp_b){
		BigNum temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;for(int i=1;i<=a[0];i++){
		int x=0;for(int j=1;j<=b[0];j++){c[i+j-1]+=a[i]*b[j]+x;x=c[i+j-1]/10;c[i+j-1]%=10;}c[i+b[0]]=x;}
		c[0]=a[0]+b[0];while(!c[c[0]]&&c[0])c[0]--;return temp_c;
	}
	friend BigNum operator + (BigNum temp_a,BigNum temp_b){
		BigNum temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;c[0]=Max(a[0],b[0])+1;
		for(int i=1;i<=c[0];i++){c[i]+=a[i]+b[i];if(c[i]>=10)c[i]-=10,c[i+1]++;}
		while(!c[c[0]]&&c[0])c[0]--;return temp_c;
	}
	friend BigNum operator - (BigNum temp_a,BigNum temp_b){
		BigNum temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;c[0]=Max(a[0],b[0]);int x=0;
		for(int i=1;i<=c[0];i++){c[i]+=a[i]-b[i];if(c[i]<0)c[i]+=10,c[i+1]--;}
		while(!c[c[0]]&&c[0])c[0]--;return temp_c;
	}
}virus[105],Mul,Plus;

int main()
{
    freopen("bzoj_1002.in","r",stdin);freopen("bzoj_1002.out","w",stdout);
	scanf("%d",&n);virus[1].set(1);virus[2].set(5);Mul.set(3);Plus.set(2);
	for(int i=3;i<=n;i++){virus[i]=virus[i-1]*Mul-virus[i-2]+Plus;}virus[n].print();
}