万径人踪灭（FFT+manacher）-白红宇

万径人踪灭（FFT+manacher）

阅读量：4577 次

发布时间：2019-06-08

本文共 3173 字，大约阅读时间需要 10 分钟。

这题……我觉得像我这样的菜鸡选手难以想出来……

题目要求求出一些子序列，使得其关于某个位置是对称的，而且不能是连续一段，求这样的子序列的个数。这个直接求很困难，但是我们可以先求出所有关于某个位置对称的子序列，最后减去子串的个数。

子串个数可以用\(manacher\)求，至于子序列的话，我们假设以第\(i\)位为中心，那么如果两边有\(x\)对相同的字符，那么这个位置对答案的贡献就是\(2^x-1\)或者\(2^(x+1)-1\)。（因为有可能回文串的长度是偶数，也就是不存在中间点）

考虑怎么求\(x_i\)。\(x_i\)的形式可以写成如下的形式：

\[\sum_{j=0}^ic[i-j] == c[i+j]\]

发现这个式子非常像卷积的形式。那么我们先初始化两个序列，第一个序列是原字符串为‘a’，对应位置为1，第二个是原字符串为'b'，对应位置是1，剩下都是0。这样结果就转化为如下形式：

\[\sum_{j=0}^i a(i-j) * a(i+j) + b(i-j) * b(i+j) \]

然后让他们自己和自己乘起来，结果相加一下，然后因为卷积会重复把元素计算两遍，所以要+1再/2.

这样得到的各项系数就是各项\(x_i\)，我们就可以用快速幂计算。算完之后减去\(manacher\)求出的子串个数即可。

看一下代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define fr friend inline#define y1 poj#define mp make_pair#define pr pair
             
              #define fi first#define sc second#define pb push_back#define I puts("bug")using namespace std;typedef long long ll;const int M = 200005;const int INF = 1000000009;const double eps = 1e-7;const double pi = acos(-1);const ll mod = 1e9+7;int read(){ int ans = 0,op = 1;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();} while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar(); return ans * op;}struct Comp{ double x,y; Comp(){} Comp(double kx,double ky){x = kx,y = ky;} fr Comp operator + (const Comp &a,const Comp &b) {return (Comp){a.x + b.x,a.y + b.y};} fr Comp operator - (const Comp &a,const Comp &b) {return (Comp){a.x - b.x,a.y - b.y};} fr Comp operator * (const Comp &a,const Comp &b) {return (Comp){a.x * b.x - a.y * b.y,a.y * b.x + a.x * b.y};}}a[M<<1],b[M<<1],kx,ky;int n,len = 1,L,p[M<<1],rev[M<<1];char s[M<<1],c[M];ll tot,d[M<<1],ans;int change(){ int l = strlen(c),j = 2; s[0] = '!',s[1] = '#'; rep(i,0,l-1) s[j++] = c[i],s[j++] = '#'; s[j] = '&'; return j;}void manacher(){ int l = change(),mx = 1,mid = 1; rep(i,1,l-1) { if(i < mx) p[i] = min(mx - i,p[(mid<<1) - i]); else p[i] = 1; while(s[i-p[i]] == s[i+p[i]]) p[i]++; if(mx < i + p[i]) mid = i,mx = i + p[i]; tot += (p[i] >> 1),tot %= mod; }}void fft(Comp *a,int f){ rep(i,0,len-1) if(i < rev[i]) swap(a[i],a[rev[i]]); for(int i = 1;i < len;i <<= 1) { Comp omg1(cos(pi / i),f * sin(pi / i)); for(int j = 0;j < len;j += (i << 1)) { Comp omg(1,0); rep(k,0,i-1) { kx = a[k+j],ky = omg * a[k+j+i]; a[k+j] = kx + ky,a[k+j+i] = kx - ky,omg = omg * omg1; } } }}ll qpow(ll a,ll b){ ll p = 1; while(b) { if(b & 1) p *= a,p %= mod; a *= a,a %= mod; b >>= 1; } return p;}int main(){ scanf("%s",c); n = strlen(c); rep(i,0,n-1) { if(c[i] == 'a') a[i].x = 1; else b[i].x = 1; } while(len <= n << 1) len <<= 1,L++; //I; rep(i,0,len-1) rev[i] = (rev[i>>1] >> 1) | ((i&1) << (L-1)); fft(a,1),fft(b,1); rep(i,0,len-1) a[i] = a[i] * a[i] + b[i] * b[i]; fft(a,-1); rep(i,0,len-1) d[i] = ((ll)floor(a[i].x / len + 0.5) + 1) >> 1; rep(i,0,len-1) ans += (qpow(2,d[i]) - 1),ans %= mod; manacher(),ans -= tot,ans %= mod; while(ans < 0) ans += mod; printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/captain1/p/10112041.html

你可能感兴趣的文章