可以把R看成顺时针转90°，O看成逆时针转270°
设R有x个，则180*(n-2)=90*x+270*(n-x)
解得R有(n+4)/2个
O有(n-4)/2个
所以n<4或者n是奇数时无解。
确定有解时，可以DP解决。
设f[第i位][R比O多j个(j的范围为-1到5)][首位是不是O][末尾是不是O]=方案数
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 LL f[1010][8][2][2];//[位数][R比O多的个数][首O][尾O] 16 const int bas=2; 17 int n; 18 int main(){ 19 int i,j,cas=0; 20 while(scanf("%d",&n) && n){ 21 printf("Case %d: ",++cas); 22 if(n&1 || n<4){printf("0\n");continue;} 23 memset(f,0,sizeof f); 24 f[1][1+bas][0][0]=f[1][bas-1][1][1]=1; 25 for(i=2;i<=n;i++){ 26 for(j=-1;j<=5;j++){ 27 f[i][j+bas][0][0]=f[i-1][j-1+bas][0][0]+f[i-1][j-1+bas][0][1]; 28 f[i][j+bas][0][1]=f[i-1][j+1+bas][0][0]; 29 f[i][j+bas][1][0]=f[i-1][j-1+bas][1][0]+f[i-1][j-1+bas][1][1]; 30 f[i][j+bas][1][1]=f[i-1][j+1+bas][1][0]; 31 } 32 } 33 LL ans=f[n][4+bas][0][0]+f[n][4+bas][0][1]+f[n][4+bas][1][0]; 34 printf("%lld\n",ans); 35 } 36 return 0; 37 }
原文：http://www.cnblogs.com/SilverNebula/p/6280409.html