修仙

· · 题解

题目简述

  • 给定长度为 m 的字符串 s，你可以插入 n 个小写字母，问最后可能得到多少个本质不同的回文串？

约定

解题思路

为了方便书写，我们下文中的 n 指生成串长度，即「题目描述」当中的 n+m。

我们先考虑 n 为偶数的情况。

首先 s 的生成串 t 的充要条件是 s 是 t 的一个子串（不一定连续）。由于我们需要生成串是回文串，我们可以考虑以子序列自动机一样贪心地去匹配。不难想到 dp：f_{i,l,r} 表示当前已经考虑生成串的前后 i 位，而且当前 s 未匹配段为 [l,r]。考虑转移：

由于 n 很大，不难想到矩阵优化。由于点数是 \mathcal O(m^2) 的，所以时间复杂度 \mathcal O(m^6\log n)。爆炸。

我们继续观察上面的 dp 转移，不难发现它本质上是在走 DAG。如例子 s=\texttt{abbac}，它对应的转移如下：

其中点旁边的数字表示自环数，\texttt ? 表示已经匹配的点。

我们需要从 [1,m] 走到 \text{goal}。不难发现当 n 较大的时候我们大部分时间都在走自环。但是不难发现「简化路径」的长度是 \mathcal O(m) 的，我们考虑从简化路径入手。

一个简化路径加上自环所产生的权值应当只与其中 24-度点的个数 u 和 25-度点的个数 v 有关。不难发现 v=\left\lceil\dfrac{n-u}{2}\right\rceil，这是因为每次经过一个 24-度点未匹配的长度就会减少 1，经过一个 25-度点未匹配的长度会减少 2，最终会达到 0 或 -1 的长度。

以此，我们只需要求出到达目标点 \text{goal} 的路径且经过 u 个 24-度点的个数 g_{\text{goal},i}，再乘上经过 u 个 24-度点和 v=\left\lceil\dfrac{n-u}{2}\right\rceil 个 25-度点组成路径的权值 val_{u,v} 即可。后面讨论 g,val 的求法。

首先 g 的求法比较简单，只要一次记忆化搜索即可。定义 g_{l,r,k} 表示在状态 [l,r] 经过 k 个 24-度点的方案数即可。

然后 val 的求法比较奇妙。首先直观的想法是推组合数，不过这个玩意不好推，我们考虑另一种方法也就是再把它变成图，变回矩阵乘法。

上图是一个 u=2,v=4 的例子。

这样子复杂度是 \mathcal O(m^4\log n) 的，依然不可接受。

但是利用矩阵乘法求出的是两两点之间长度一定的路径数量，不难可以把所有的路径合成一个更大的图，如下图所示：

实际上把所有边反过来更符合上面的图，不过代码使用的是这张图的建模。

当我们需要查询 2 个红点，4 个蓝点之间的答案时，只需要调用红点上面的「目标点」和对应蓝点之间矩阵的数值即可。

这下可以做到 \mathcal O(m^3\log n) 求出 val。

最终时间复杂度为 \mathcal O(m^3\log n)，轻微卡常。

别忘了我们上面假设了 n 为偶数，当 n 为奇数的时候只要减去 n-1 步时还有一步到终点的方案即可。

代码实现

不严谨的来说，直接暴力建是 \mathcal O((3m)^3\log n) 的，显然过不去。但是注意到 v 的值域比较小，这样我们只用建一半左右，矩阵变到 2m。然后这个矩阵还是三角矩阵，容易优化一个 \dfrac16 的常数，得以通过。

还要注意的是 n 为偶数时需要求出 n-1 步的矩阵，这里不用两次矩阵快速幂。只要求出 A^{n-1} 再乘上 A 就可以得到 A^n 了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define int youzi_xinzuo_jijiji
const int MAXN=205;
const int MOD=10007;
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;} 
int n,m,sz;
string s;
int rep_24[MAXN],rep_25[MAXN],rep_goal[MAXN];
int f[MAXN][MAXN][MAXN];// f[l,r,k] 从 [l,r] 到 goal 经过 k 个 24- 节点的方案数 
struct matrix{
int a[MAXN<<1][MAXN<<1];
matrix(){memset(a,0,sizeof(a));}
friend matrix operator *(matrix x,matrix y){
    matrix z;
    for(int i=1;i<=sz;i++)
        for(int k=i;k<=sz;k++) if(x.a[i][k])
            for(int j=k;j<=sz;j++)
                add(z.a[i][j],x.a[i][k]*y.a[k][j]%MOD);
    return z;
} 
}A,B;
matrix ksm(matrix a,int b){matrix res;for(int i=1;i<=sz;i++)res.a[i][i]=1;while(b){if(b&1)res=res*a;a=a*a,b>>=1;}return res;} 
void build(){
    for(int i=(n+1)/2;i>=1;i--){
        rep_goal[i]=++sz;rep_25[i]=++sz;
        if(i<(n+1)/2) A.a[rep_25[i+1]][rep_25[i]]=1;
        A.a[rep_25[i]][rep_25[i]]=25;
        A.a[rep_goal[i]][rep_25[i]]=1;
    } 
    A.a[rep_25[1]][rep_goal[0]=++sz]=1;
    for(int i=1;i<=n;i++){
        rep_24[i]=++sz,
        A.a[rep_24[i]][rep_24[i]]=24;
        if(i>1) A.a[rep_24[i-1]][rep_24[i]]=1;
    } 
    A.a[rep_25[1]][rep_24[1]]=1;
    for(int i=0;i<=n;i++) A.a[rep_goal[i]][rep_goal[i]]=26;
    B=ksm(A,(m+1)/2-1),A=B*A;
    return;
}
int query(int x,int y){return A.a[rep_goal[x]][(y?rep_24[y]:rep_25[1])];}// x 25, y 24  
int query1(int x,int y){return B.a[rep_25[x]][(y?rep_24[y]:rep_25[1])];}// x 25, y 24  
int dfs(int l,int r,int k){
    if(k<0) return 0;
    if(f[l][r][k]>=0) return f[l][r][k];
    if(l>r) return (k==0);
    int ans=0;
    if(s[l]==s[r]) ans=dfs(l+1,r-1,k);
    else ans=(dfs(l+1,r,k-1)+dfs(l,r-1,k-1))%MOD;
    return (f[l][r][k]=ans);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>s>>m;n=s.length(),m+=n;
    s=" "+s;
    build();
    memset(f,-1,sizeof(f));
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans+=dfs(1,n,i)*query((n-i+1)/2,i)%MOD;
        if((m&1)&&(n-i)%2==0) ans-=dfs(1,n,i)*query1((n-i+1)/2,i)%MOD;
    }
    cout<<(ans%MOD+MOD)%MOD;
    return 0;
}