12785 神秘代码FZ

题目描述:
Farmer John有一段长度至少为2的仅由大写字母组成的代码,现在他要对这段代码进行一次或一次以上的骚操作。对于一段代码S,Farmer John可以有如下的骚操作:把S的开头一个字母或结尾一个字母去掉,接在S的开头或结尾作为新的代码。例如ABCD经过一次骚操作可以变成的代码有:BCDABCD、ABCDBCD、ABCABCD、ABCDABC。
再举一个例子,ABA经过一次骚操作可以变成的代码有:BAABA、ABABA、ABABA、ABAAB。
尽管ABABA和ABABA看起来是相同的,但由于它是由不同的方式拼接而来,我们认为这两种是不同的方案。
现在给出Farmer John进行了一次或一次以上骚操作的代码,你需要计算可能的操作出这段代码的方案数。

暴力枚举,每个段能从那个段转移过来,递归实现即可。

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
int len;
char s[100005]; 
long long sou(int l,int r)
{
//  printf("%d %d\n",l,r);
    int Len=r-l+1;
    if(Len%2==0) return 1;
    long long ans=1;
    int m=(l+r)/2;
    int ll=0,rr=0;
    bool bo=true;
    for(int i=l,j=m+1;i<m&&j<=r;i++,j++)
    {
        if(s[i]!=s[j])
            bo=false;
    }
    if(bo) ll++,rr++;
    bo=true;
    for(int i=l+1,j=m+1;i<=m&&j<=r;i++,j++)
    {
        if(s[i]!=s[j])
            bo=false;
    }
    if(bo) ll++;
    bo=true;
    for(int i=l,j=m;i<m&&j<r;i++,j++)
    {
        if(s[i]!=s[j])
            bo=false;
    }
    if(bo) rr++;
    if(ll) ans+=ll*sou(l,m);
    if(rr) ans+=rr*sou(m,r);
    return ans;
}
int main()
{
    scanf("%s",s);
    len=strlen(s);
    printf("%lld",sou(0,len-1)-1);
}