请看下面的转换图：
其中红线表示非法转换，蓝线表示合法转换。这样就可以构建4x4的矩阵了。
接下来快速幂...ac。
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;struct node
{ int m[4][4]; }res,temp,mod;int n;node matriXmult( node a,node b )
{node c;memset( c.m,0,sizeof(c.m) );for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )for( int k=0;k<4;k++ )c.m[i][j]+=a.m[i][k]*b.m[k][j];for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )c.m[i][j]%=2005;return c;
}void matrix_Power()
{memset( res.m,0,sizeof(res.m) );memset( temp.m,0,sizeof(temp.m) );for( int i=0;i<4;i++ ){res.m[i][i]=1;for( int j=0;j<4;j++ )temp.m[i][j]=mod.m[i][j];}for( int i=0;i<31;i++ ){if( n&(1<<i) )res=matriXmult(res,temp);temp=matriXmult(temp,temp);}
}
int main()
{memset( mod.m,0,sizeof(mod.m) );mod.m[0][0]=mod.m[0][1]=mod.m[1][2]=mod.m[1][3]=1;mod.m[2][0]=mod.m[3][2]=1;while( scanf("%d",&n)!=EOF ){if( n==1 ){printf("2\n");continue;}if( n==2 ){printf( "4\n");continue;}n-=2;matrix_Power();int sum=0;for( int i=0;i<4;i++ )for( int j=0;j<4;j++ )sum+=res.m[i][j];printf( "%d\n",sum%2005 );}
}