#include <stdio.h>
#include <memory.h>
__int64 a[20][16][5][2];
int flag[5] = {0,1,2,4,8};
void init()
{
int i;
memset(a,-1,sizeof(a));
for(i=0;i<=15;i++)
{
a[1][i][1][1] = a[1][i][2][1] = a[1][i][3][1] = a[1][i][4][1] = 0;
a[1][i][1][0] = a[1][i][2][0] = a[1][i][3][0] = a[1][i][4][0] = 0;
}
a[1][1][1][0] = 1;
a[1][2][2][0] = 1;
a[1][4][3][0] = 1;
a[1][8][4][0] = 1;
}
__int64 ado(int n,int p,int k,int u)
{
int t;
if(n<=0) return 0;
if(a[n][p][k][u]!=-1) return a[n][p][k][u];
a[n][p][k][u] = 0;
if((p&flag[k])==0) return 0;
t = p&~flag[k];
if(u==0)
{
if(k==1)
{
a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(n-1,p,3,0);
a[n][p][k][u] += ado(n-1,t,1,0) + ado(n-1,t,2,0) + ado(n-1,t,3,0);
}
else if(k==4)
{
a[n][p][k][u] += ado(n-1,p,2,0) + ado(n-1,p,3,0) + ado(n-1,p,4,0);
a[n][p][k][u] += ado(n-1,t,2,0) + ado(n-1,t,3,0) + ado(n-1,t,4,0);
}
else
{
a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(n-1,p,3,0) + ado(n-1,p,4,0);
a[n][p][k][u] += ado(n-1,t,1,0) + ado(n-1,t,2,0) + ado(n-1,t,3,0) + ado(n-1,t,4,0);
}
}
else
{
a[n][p][k][u] += ado(n-1,p,1,1) + ado(n-1,p,2,1) + ado(n-1,p,3,1) + ado(n-1,p,4,1);
a[n][p][k][u] += ado(n-1,t,1,1) + ado(n-1,t,2,1) + ado(n-1,t,3,1) + ado(n-1,t,4,1);
if(k==1)
{
a[n][p][k][u] += ado(n-1,p,4,0);
a[n][p][k][u] += ado(n-1,t,4,0);
}
if(k==4)
{
a[n][p][k][u] += ado(n-1,p,1,0);
a[n][p][k][u] += ado(n-1,t,1,0);
}
}
return a[n][p][k][u];
}
int main()
{
int n,i;
__int64 sum;
init();
while(scanf("%d",&n)&&n!=-1)
{
for(i=1,sum=0;i<=4;i++)
{
sum += ado(n,7,i,1);
sum += ado(n,11,i,1);
sum += ado(n,13,i,1);
sum += ado(n,14,i,1);
sum += ado(n,15,i,1);
}
printf("%d: %I64d\n",n,sum);
}
return 0;
}
本栏目所有文章均为原创,转载请注明来源:http://insky.programfan.com
评论