万径人踪灭

Description

Input

Output

Sample Input

Sample Output

HINT

千山鸟飞绝
思路特别好的一道题~学习一个

思路:
可以发现这个“不连续的回文子序列”不好求。
那么考虑容斥，用“所有的回文子序列”减去“所有的回文子串”即可。

后者很显然是个Manacher。
前者的话，考虑设f[i]表示以i为对称中心的对称字符对数。
则答案为∑2f[i]?1。

考虑如何求f数组:
先令所有a为1,b为0，做一遍FFT。
再令所有b为1,a为0，做一遍FFT。
两边FFT的和+1后除以2就是f数组。

那这就做完了~

#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long ll;
typedef double db;
typedef complex cp;
const int N=400009;
const ll md=1e9+7;
const db pi=3.1415926535897;

int n,m,l;
int p[N],rev[N];
ll f[N],ans;
cp a[N],b[N];
char s[N],ch[N];

inline ll qpow(ll a,ll b)
{
    ll ret=1ll;
    while(b)
    {
        if(b&1ll)
            ret=ret*a%md;
        a=a*a%md;
        b>>=1;
    }
    return ret;
}

inline void FFT(cp *a,int n,int f)
{
    for(int i=0;i=0 && ch[i+p[i]]==ch[i-p[i]])
            p[i]++;
        if(i+p[i]-1>mx)
            mx=i+p[i]-1,mp=i;
    }

    for(int i=0;i<=m;i++)
        ans=(ans-(p[i]>>1)+md)%md;

    for(m=1,l=0;m<=(n<<1);m<<=1)l++;
    for(int i=0;i>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i>1)-1+md)%md;

    printf("%lld\n",ans);
    return 0;
}