hdoj 2047 简单递推

代码：

#include <stdio.h>
int main()
{
 int n,m,i;
 __int64 x[41];
 x[1]=3;
 x[2]=8;
 for(i=3;i<=40;i++)
        x[i]=2*(x[i-1]+x[i-2]);
 while(scanf("%d",&n)!=EOF)
 { 
  printf("%I64d ",x[n]);
 }
 return 0;
}

证明：i个字符共有x[i]种排列方法，设其中结尾为o和结尾不为o的为a[i],b[i]种，

x[i]=a[i]+b[i];

a[i]=b[i-1];

b[i]=2*x[i-1];

求得：x[i]=2*(x[i-1]+x[i-2]);