记录编号	38822	评测结果	AAAAAATTTA
题目名称	小D的背包问题	最终得分	70
用户昵称	Czb。	是否通过	未通过
代码语言	C++	运行时间	3.128 s
提交时间	2012-06-14 21:46:29	内存使用	0.29 MiB

#include<stdio.h>
 
int n,f[2][20];
 
int main()
{
	freopen("baga.in","r",stdin);
	freopen("baga.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    f[0][15]=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=15;j++)
        {
            f[i&1][j]=f[!(i&1)][j^15];
        }
        for(j=0;j<=15;j++)
        {
            if((j&3)==3)
                f[i&1][j]=(f[i&1][j]+f[i&1][j^3])%997;
            if((j&(3<<1))==(3<<1))
                f[i&1][j]=(f[i&1][j]+f[i&1][j^(3<<1)])%997;
            if((j&(3<<2))==(3<<2))
                f[i&1][j]=(f[i&1][j]+f[i&1][j^(3<<2)])%997;
        }
        f[i&1][15]-=f[i&1][0];
		if(f[i&1][15]<0)f[i&1][15]+=997;
    }
    printf("%d\n",f[n&1][15]);
    return 0;
}