记录编号	185233	评测结果	AAAAAAAAAA
题目名称	[FJOI 2007] 轮状病毒	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2015-09-05 10:34:20	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=101;
const int maxl=51;
struct Matrix{
	int a[maxn];
	int l;
	
	Matrix operator / (int x){
        Matrix b;
		for(int i=1;i<=l;i++){
			b.a[i]+=a[i]*x;
			b.a[i+1]+=b.a[i]/10;
			b.a[i]%=10;
		}
		if (b.a[l+1]) b.l=l+1; else b.l=l;
		return b;
	}
	
	Matrix operator * (Matrix x){
        Matrix b;
		for(int i=1;i<=l;i++){
			int t=0;
			for(int j=1;j<=x.l;j++){
				int &k=b.a[i+j-1];//&k
				k+=a[i]*x.a[j]+t;
				t=k/10;  k%=10;
			}
			if (t) b.a[i+x.l]+=t;
		}
		if(b.a[l+x.l]) b.l=l+x.l;
		else b.l=l+x.l-1;
		return b;
	}
	
	Matrix operator - (Matrix x){
		Matrix b;
		for (int i=1;i<=l;++i){
			b.a[i]+=a[i]-x.a[i];//+=
			if (b.a[i]<0){
				b.a[i]+=10;
				b.a[i+1]-=1;
			}
		}
		if (b.a[l]) b.l=l;
		else b.l=l-1;
		return b;
	}
	
	Matrix (){l=1;memset(a,0,sizeof(a));}
};

int n,m;

int main()
{
	freopen("bzoj_1002.in","r",stdin);
	freopen("bzoj_1002.out","w",stdout);
	scanf("%d",&n);
	Matrix M[maxn];
	M[1].a[1]=1,M[2].a[1]=1,M[3].a[1]=4;
	for(int i=4;i<=n;i++)
	   M[i]=M[i-2]/3-M[i-4];
	M[n]=M[n]*M[n];
	if (~n&1) M[n]=M[n]/5;
	for (int i=M[n].l;i!=0;--i)
		printf("%d",M[n].a[i]);
}