代码:
#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\n",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]);