CF506E 题解 $\text{Description}$ 给定字符串 $S$ 和正整数 $n$，求有多少个回文字符串 $T$ 满足 $|T|=|S|+n$ 且 $S$ 是 $T$ 的一个子序列。
$|S|\le 200,n\le 10^9$
$\text{Solution}$ 一眼看过去就很矩阵快速幂……所以直接 BM 加线性递推 $O(|S|^3+|S|^2\log n)$。
由于 $T$ 是回文字符串，所以我们考虑在两边同时加字符，并且我们先考虑 $|T|$ 为偶数的情况。
设 $f(l,r,k)$ 表示已经填好了 $T$ 的左边及右边各 $k$ 位，且 $S$ $[l,r]$ 尚未匹配进 $T$ 的方案数，我们发现这样遗漏了 $S$ 已经完全匹配的情况，所以额外设 $g(k)$ 表示已经填好了 $T$ 的左边及右边各 $k$ 位且 $S$ 已经完全匹配的方案数。
这样的话容易得到转移方程，此处不赘述转移方程，但是会说推导过程。
如果此时 $S_l=S_r$，若 $r=l+1$ 或 $r=l$，它有两种选择，一种是直接匹配好（当 $r=l+1$ 且 $|T|$ 为偶数时是不可以在 $k=\lfloor\frac{|T|}{2}\rfloor$ 时进行的），一种是不匹配，填剩下的 $25$ 个字符；若 $r>l+1$，它仍有两种选择，一种是匹配掉 $l,r$，一种是不匹配，填剩下的 $25$ 个字符。
如果此时 $S_l\neq S_R$，我们仍有两种选择，一种是匹配掉其中一个（注意这里有两种转移），一种是不匹配，填剩下的 $24$ 个字符。
最后还有已经匹配完 $S$ 的情况，这个就是随便填 $26$ 种字符。
这样设计出来的转移方程复杂度极其之高。不过我们注意到 $k$ 那一维是开销最大的，而且它只会进行 $k+1\gets k$ 的转移，如果我们认为 $(l,r)$ 是一个点，然后按照转移关系连有向边（从 $A$ 转移到 $B$ 就是 $A\rightarrow B$），除了自环，其它的边由于都是大区间连向小区间，故形成了一个 DAG。而 $k$ 那一维的意义在此时就变成了从 $[1,|S|]$ 出发，到达 $g$ 时走了 $k$ 条边的方案数，这个可以用矩阵快速幂优化对吧，时间复杂度高达 $|S|^6\log (n+|S|)$，虽然优化很大，但不能过。
我们常常有一个优化手段，叫作 “适当合并等价信息”，或者说考虑某一类元素，它们的贡献是相同的，那么这一类元素的总贡献就是元素个数乘上单个元素的贡献。再来看一下我们的图有什么特点，它除了 DAG，还有自环……自环！而且每个点的自环数只有 $24,25,26$ 三种情况，并且只有终点有 $26$ 个自环。我们把一个点称作 “$x$点” 当且仅当这个点有 $x$ 个自环。更重要的是，一个 $24$ 点会让当前代表区间缩小 $1$，而一个 $25$ 点会让当前代表区间缩小 $2$（有一个特例是 $r=l$），我们的区间长度为 $|S|$，说明一条从起点（$[1,n]$）出发到终点的路径上，若有 $x$ 个 $24$ 点，那么就有 $\lceil\frac{|S|-x}{2}\rceil$（上取整正是考虑到了那个特例）个 $25$ 点。不过最最重要，使得我们能合并所有 $24$ 点个数相同的合法路径的条件是：各种点的排列不影响答案。于是我们记 $cnt(i,l,r)$ 表示起点到 $[l,r]$ 的路径上有 $i$ 个 $24$ 点的数量（提一嘴，这个东西在偶数情况下的终止状态为 $r-l\le 1$），就可以 $O(|S|^3)$ DP出等价类元素个数。那么怎么计算某个等价类里单个元素的贡献呢？我们发现只需搞出来一条链，前面都是 $24$ 点，后面除了终点其它都是 $25$ 点，然后对这个链作矩阵快速幂即可。由于链有 $O(|S|)$ 个，长度为 $O(|S|)$，故复杂度为 $O(|S|^4\log (n+|S|))$，还需继续努力。
我们发现这些链其实共同点很多，能不能合并一下，一个矩阵快速幂计算完答案呢？当然可以，只需把 $24$ 点总数个点（上）和 $25$ 点总数个点（下）都列出来，然后形成两条链，链上边数都为 $1$，接着考虑跨链连边，若是第 $k$ 个 $24$ 点向下连边，那么就要让右边的 $25$ 点数量和 $24$ 点对应起来就可以了，注意这里边数不能是 $1$，而是这个等价类里元素的个数，这是为了方便计算。现在这个图上就只有 $O(|S|) $ 个点了，而我们只要做一次矩阵快速幂，复杂度为 $O(|S|^3\log (n+|S|))$。
偶数讨论完了，还剩奇数的情况。当 $|T|$ 为奇数时，大体一样，但是回忆上面的转移，有提到过一个向终点的转移只能在 $|T|$ 为偶数时进行，我们先按照偶数的情况计算，然后减去这一情况的数量即可。怎么设计才能做到最后一条边是由那个转移变化来的呢？首先要去掉终点的自环，然后要让 $24$ 点向 $25$ 点连的边数只有形如 $cnt(i,l,l+1)$ 的和，因为我们只需去掉这种情况的转移，然后再做一次矩阵快速幂即可。
常数的优化呢只需注意 “小点连向大点”，所以矩阵都是上三角矩阵，操作时可以不去考虑下三角部分。
$\text{Code}$ 代码参考自 @xht37。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include <bits/stdc++.h> #define REG register #define MAXL 305 using namespace std ;const int Mod=10007 ;inline void read (int & x) static char c; while (!isdigit (c=getchar()));x=c^48 ; while (isdigit (c=getchar()))x=(x*10 )+(c^48 ); } inline int Add (int a,int b) return (a+b)%Mod;}inline int Del (int a,int b) return (a-b+Mod)%Mod;}char str[MAXL];int s,m,n;int G[MAXL][MAXL],Ans[MAXL],Cnt[MAXL][MAXL][MAXL];int TmpG[MAXL][MAXL],TmpAns[MAXL];inline void VMulM () int R[MAXL];memset (R,0 ,sizeof R); for (REG int j=1 ;j<=m;++j) for (REG int i=1 ;i<=m;++i) R[i]=Add(R[i],Ans[j]*G[j][i]%Mod); for (REG int i=1 ;i<=m;++i) Ans[i]=R[i]; } inline void MMulM () int R[MAXL][MAXL];memset (R,0 ,sizeof R); for (REG int i=1 ;i<=m;++i) for (REG int k=i;k<=m;++k) for (REG int j=k;j<=m;++j) R[i][j]=Add(R[i][j],G[i][k]*G[k][j]%Mod); for (REG int i=1 ;i<=m;++i) for (REG int j=1 ;j<=m;++j) G[i][j]=R[i][j]; } int GetCnt (int Stp,int l,int r) if (Stp<0 ) return 0 ; if (~Cnt[Stp][l][r]) return Cnt[Stp][l][r]; Cnt[Stp][l][r]=0 ; if (l==1 &&r==s) return Cnt[Stp][l][r]=!Stp; if (l^1 &&str[l-1 ]^str[r]) Cnt[Stp][l][r]=Add(Cnt[Stp][l][r],GetCnt(Stp-1 ,l-1 ,r)); if (r^s&&str[l]^str[r+1 ]) Cnt[Stp][l][r]=Add(Cnt[Stp][l][r],GetCnt(Stp-1 ,l,r+1 )); if (l^1 &&r^s&&str[l-1 ]==str[r+1 ]) Cnt[Stp][l][r]=Add(Cnt[Stp][l][r],GetCnt(Stp,l-1 ,r+1 )); return Cnt[Stp][l][r]; } inline void Pow (int b) while (b){ if (b&1 ) VMulM(); MMulM(),b>>=1 ; } } inline void Work () memset (Cnt,-1 ,sizeof Cnt); scanf ("%s" ,str+1 ); s=strlen (str+1 ),m=s+(s+1 )/2 ; read(n); for (REG int i=0 ;i<s;++i){ int C=0 ; for (REG int j=1 ;j<=s;++j){ C=Add(C,GetCnt(i,j,j)); if (j^s&&str[j]==str[j+1 ]) C=Add(C,GetCnt(i,j,j+1 )); } if (i){ G[i][m-(s-i+1 )/2 ]=C,G[i][i]=24 ; if (i^1 ) G[i-1 ][i]=1 ; else Ans[i]=1 ; } else { Ans[s]=C,G[m][m]=26 ; for (REG int j=s;j<m;++j) G[j][j+1 ]=1 ,G[j][j]=25 ; } } if ((n+s)&1 ){ for (REG int i=1 ;i<=m;++i) TmpAns[i]=Ans[i]; for (REG int i=1 ;i<=m;++i) for (REG int j=1 ;j<=m;++j) TmpG[i][j]=G[i][j]; } Pow((n+s+1 )/2 ); if ((n+s)&1 ){ int Sum=Ans[m]; for (REG int i=1 ;i<=m;++i) Ans[i]=TmpAns[i]; for (REG int i=1 ;i<=m;++i) for (REG int j=1 ;j<=m;++j) G[i][j]=TmpG[i][j]; for (REG int i=0 ;i<s;++i){ int C=0 ; for (REG int j=1 ;j<=s;++j) if (j^s&&str[j]==str[j+1 ]) C=Add(C,GetCnt(i,j,j+1 )); if (i) G[i][m-(s-i+1 )/2 ]=C; else Ans[s]=C,G[m][m]=0 ; } Pow((n+s+1 )/2 ); printf ("%d\n" ,Del(Sum,Ans[m])); } else printf ("%d\n" ,Ans[m]); getchar(); } int main ()
