LG P4199 万径人踪灭

Description

在只含a,b的字符串中，求满足以下条件的子序列个数：

位置和字符关于某条对称轴对称
不能是连续的一段

Solution

答案可以转化为关于某条对称轴对称的子序列-连续的回文串

连续的回文串可以用Manacher求出

关于某条对称轴对称的子序列可以FFT求出：将原字符串中为a的位置设为1，b的位置设为0，该多项式自平方后第$i$位即为以$frac{i}{2}$为对称轴，左右两边相同位置为a的对数$x$，b同理，则分奇偶讨论可得以该对称轴为中心有$2^{x+1}-1$或$2^x-1$个字母组合满足条件

FFT多项式相乘

#include<iostream>
#include<cstring>
#include<complex>
#include<cstdio>
#include<cmath>
using namespace std;
long long len,rev[400005],tot=1,s=2,ans[400005],r[400005],sum;
const long long mod=1000000007;
const double pi=acos(-1);
char str[400005],sn[400005];
complex<double>an[400005],bn[400005];
inline long long read()
{
    long long w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
void fft(complex<double>*a,long long n,long long inv)
{
    for(long long i=0;i<n;i++)
    {
        if(i<rev[i])
        {
            swap(a[i],a[rev[i]]);
        }
    }
    for(long long i=1;i<n;i<<=1)
    {
        complex<double>wn=exp(complex<double>(0,inv*pi/i));
        for(long long j=0;j<n;j+=i*2)
        {
            complex<double>w(1,0);
            for(long long k=j;k<i+j;k++)
            {
                complex<double>x=a[k],y=w*a[k+i];
                a[k]=x+y;
                a[k+i]=x-y;
                w*=wn;
            }
        }
    }
    if(inv==-1)
    {
        for(long long i=0;i<n;i++)
        {
            a[i]/=n;
        }
    }
}
long long ksm(long long a,long long p)
{
    long long ret=1ll;
    while(p)
    {
        if(p&1)
        {
            (ret*=a)%=mod;
        }
        (a*=a)%=mod;
        p>>=1;
    }
    return ret;
}
void manacher()
{
    long long nlen=0,maxx=0,maxlen=-1,id;
    sn[nlen]='$';
    sn[++nlen]='#';
    for(long long i=0;i<len;i++)
    {
        sn[++nlen]=str[i];
        sn[++nlen]='#';
    }
    sn[++nlen]='

LG P4199 万径人踪灭

Description

Solution

相关推荐