记录编号	152081	评测结果	AAAAAAAAAA
题目名称	813.小D的背包问题	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-03-12 21:28:51	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int Mod =997,N =16;

struct MA{
	int a[21][21],n,m;
	void init(int x,int y){
		n=x; m=y;
		memset(a,0,sizeof(a));
	}
	MA operator*(const MA &x)const{
		MA re;
		re.init(n,x.m);
		for(int i=1;i<=re.n;i++)
			for(int j=1;j<=re.m;j++)
				for(int k=1;k<=m;k++)
					re.a[i][j]=(re.a[i][j]+a[i][k]*x.a[k][j])%Mod;
		return re;
	}
	void operator*=(const MA &x){*this=*this*x;}
	void print(){
		cout<<"Matrix : "<<n<<' '<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				cout<<a[i][j]<<' ';
			cout<<endl;
		}
	}
}A,Ans;

MA qpow(MA &x,int n){
	MA re,tp=x;
	re.init(N,N);
	for(int i=1;i<=N;i++) re.a[i][i]=1;
	for(;n;n>>=1,tp*=tp) if(n&1) re*=tp;
	return re;
}

void dfs(int t,int now,int pre){
	if(t==4) A.a[pre+1][now+1]++;
	if(t>=4) return;
	dfs(t+1, (now<<1)|1, (pre<<1)  );	//2*1
	dfs(t+1, (now<<1),   (pre<<1)|1);
	dfs(t+2, (now<<2)|3, (pre<<2)|3);	//1*2
}

int n;

int main(){
	freopen("baga.in","r",stdin);
	freopen("baga.out","w",stdout);
	scanf("%d",&n);
	A.init(N,N);
	dfs(0,0,0);
	Ans=qpow(A,n);
	printf("%d\n",Ans.a[N][N]);
}