C. 字符序列

简要题意：有一个函数 \(f(c,s)=cs_1cs_2cs_3\cdots cs_nc\)。给出操作序列 \(c_i\)，每次操作使 \(s=f(c_i,s)\)（\(s\) 开始为空串），求最后的字符串中有多少个本质不同的子序列。

数据范围： \(n\le 500\)。

首先我们可以考虑一个简化经典问题，已知一个字符串，求本质不同的子序列数量。

因为我们需要把所有本质不同的子序列在字符串中找到唯一的映射，所以我们贪心的钦定每个字符都取字符串中第一个出现的，而不取第二次出现的。

可设 \(f_{i,j}\) 表示考虑完了 \(i\cdots n\) 的字符，开头为 \(j\) 的本质不同子序列数量。

\(f_{i,j}=\begin{cases}f_{i+1,j}&a_i\ne j\\\sum\limits_c f_{i+1,c}+1&a_i=j\end{cases}\)

假如已知这个字符串，\(O(N\left\vert \sum\right\vert)\) 转移即可。放在这题中可以得到 50pts。

考虑正解，显然字符串非常大，无法求出，我们观察每次操作的字符串之间有什么规律。

a
bab
cbcacbc
dcdbdcdadcdbdcd

我们容易发现，若设 \(T_i\) 为 \(i\) 到 \(n\) 操作后的序列，那么字符串的变化可以写成 \(T_i=T_{i+1}+c_i+T_{i+1}\)。最终字符串即为 \(T_1\)。

回到 \(dp\)，转移方程为求和的形式，只由 \(i+1\) 转移过来，容易写成矩阵转移的形式，虽然在已知字符串的情况下复杂度为 \(O(N\left\vert \sum\right\vert^3)\)，但是它不需要顺推，在对于有规律的字符串变化中可以直接矩阵转移。

复杂度为 \(O(n\left\vert \sum\right\vert^3)\)。