记录编号	38832	评测结果	AAAAAAAAAA
题目名称	小D的背包问题	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-06-15 09:29:59	内存使用	0.31 MiB

/*
Type: 递推,验证公式,通用解是状态压缩的dp
*/
#include <fstream>
#include <cstdlib>
#include <memory.h>
using namespace std;
ifstream fin("baga.in");
ofstream fout("baga.out");
int N,f[5],r[5][5],d[5][5];
 
void Bs(int x)
{
    if(x<=1)
        return;
    else
        Bs(x/2);
int i,j,k,temp[5][5];
    memset(temp,0,sizeof(temp));
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
            for(k=1;k<=4;k++)
            {
                temp[i][j]+=(r[k][j]*r[i][k])%997;
                temp[i][j]%=997;
            }
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
            r[i][j]=temp[i][j];
    if(x%2==1)
    {
        memset(temp,0,sizeof(temp));
        for(i=1;i<=4;i++)
            for(j=1;j<=4;j++)
                for(k=1;k<=4;k++)
                {
                    temp[i][j]+=(r[k][j]*d[i][k])%997;
                    temp[i][j]%=997;
                }
        for(i=1;i<=4;i++)
            for(j=1;j<=4;j++)
                r[i][j]=temp[i][j];
    }
}
 
void dt()
{
int i,j;
	for(i=1;i<4;i++)
		r[i+1][i]=1;
	r[1][4]=-1;r[2][4]=1;r[3][4]=5;r[4][4]=1;
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
			d[i][j]=r[i][j];
    f[0]=1;f[1]=1;f[2]=5;f[3]=11;
	if(N<=3)
	{
		fout<<f[N]<<endl;
		return;
	}
    Bs(N);
     
int temp[5];memset(temp,0,sizeof(temp));
    for(i=1;i<=4;i++)
        for(j=1;j<=4;j++)
        {
            temp[i-1]+=(f[j-1]*r[j][i])%997;
            temp[i-1]=temp[i-1]%997;
			if(temp[i-1]<0)temp[i-1]=997+temp[i-1];
        }
	
    fout<<temp[0]<<endl;
}
 
int main()
{
    fin>>N;
     
    dt();
     
    fin.close();
    fout.close();
    return 0;
}