给定一个串，把串分为偶数段
假设分为了(s1,s2,s3....sk)
求，满足(s_1=s_k,s_2=s_{k-1}......) 的方案数
((2le|s|le10^{6}))
PAM好题QAQ
我们先把题目要求转化成回文串，假设分成了 (k) 段为 (s_1,s_2,s_3dots s_k) ，我们单独看 (s_1) 和 (s_k) ，假设他们的长度是 (x) ，那么对于原串 (a) 就有：
于是我们构造一个串 (b=a_1a_na_2a_{n-1}a_3a_{n-2}dots) ，这样子我们求长度为偶数且总和为 (n) 的回文串方案数就可以了。
然后我们考虑dp，设 (f_i) 表示以 (i) 结尾的方案数，那么就有 (f_i=sum_jf_{j-1}) ，其中 ([j,i]) 于是我们一直跳 (fail) 就可以得到所有的 (j) 。
但是这样子做过不去的，全是相同字符就会退化到 (O(n^2)) ，于是我们再进一步考虑。
对于字符串 (border) 有：一个字符串的所有 (border) 会形成 (log) 个不相交的等差数列。
考虑证明，我们对于比 (frac{len}{2}) 大的两个 (border) (A,B) ，假设 (B) 是该串的最长 (border) ，那么 (len-|B|) 是其最小周期，那么 (len-|B| | len-|A|) ，于是对于所有满足 (s=k(len-|B|),len-sge len) 的都是字符串的 (border) ，然后递归考虑 (frac{len}{2}) 的问题就可以了。
那么对于回文串，我们显然有如果一个串 (S) 的后缀 (T) 是回文的，那么 (T) 是 (S) 的 (border) ，于是我们通过这个来优化复杂度。
设 (g_p) 表示以 (p) 这个结点结束的等差数列的贡献，具体点就是如果这段等差数列长度分别为 (s_1,s_2,dots s_k) ，那么 (g_p=sum_{i=1}^kf_{x-s_i}) ，(x) 是当前位置。
于是我们考虑求这个东西，根据回文串的性质，发现 (g_p=g_{fail[p]}+f_{x-s_k}) ，因为 (fail_p) 会把 (p) 之前的都算到，然后加上自己的贡献就可以了，这样子复杂度就变成了 (O(nlog n))
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e6;
const int mod = 1e9 + 7;
using namespace std;
int n;
char s[N + 5],ns[N + 5];
struct PAM
{
int ch[N + 5][26],fail[N + 5],len[N + 5],nc,las,f[N + 5],sf[N + 5],d[N + 5],pos[N + 5];
char s[N + 5];
void init(char *ch)
{
for (int i = 1;i <= n;i++)
s[i] = ch[i];
s[0] = '#';
len[1] = -1;
pos[0] = 1;
fail[0] = 1;
f[0] = 1;
nc = 1;
}
void insert(int x)
{
int p = las;
while (s[x - len[p] - 1] != s[x])
p = fail[p];
if (!ch[p][s[x] - 'a'])
{
len[++nc] = len[p] + 2;
int j = fail[p];
while (s[x - len[j] - 1] != s[x])
j = fail[j];
fail[nc] = ch[j][s[x] - 'a'];
d[nc] = len[nc] - len[fail[nc]];
if (d[nc] == d[fail[nc]])
pos[nc] = pos[fail[nc]];
else
pos[nc] = fail[nc];
ch[p][s[x] - 'a'] = nc;
}
las = ch[p][s[x] - 'a'];
int j = las;
while (j > 1)
{
sf[j] = f[x - len[pos[j]] - d[j]];
if (pos[j] != fail[j])
sf[j] += sf[fail[j]],sf[j] %= mod;
if (x % 2 == 0)
f[x] += sf[j],f[x] %= mod;
j = pos[j];
}
}
void build()
{
for (int i = 1;i <= n;i++)
insert(i);
}
}pa;
int main()
{
scanf("%s",s + 1);
n = strlen(s + 1);
int l = 1,r = n;
for (int i = 1;i <= n;i++)
if (i % 2 == 1)
ns[i] = s[l++];
else
ns[i] = s[r--];
pa.init(ns);pa.build();
cout<<pa.f[n]<<endl;
return 0;
}