[南海云课堂] [DP] [方案数计数] [问题转换] 同义串

_Cheems · 2023-08-16 21:17:41 · 个人记录

洛谷链接

题意

对于单词（字符串） s ，保证它只由小写字母组成。

设 s 的长度为 len ，下文单词（字符串）下标从 1 开始.

如果一个词可以通过零次或多次运算转换成另一个词，则我们认为这两个词的意思是一致的。

运算仅仅包含以下两种方式。

• 方式一：指定任意一个位置 p (1 \le p \le len)使 s_p 上的字母变成 字母表上 的后一个字母(如 a 变成 b ，x 变成 y)，而 s_{p+1} 则要变成 字母表上 的前一个字母(如 d 变成 c)。
• 方式二：指定任意一个位置 p (1 \le p \le len)使 s_p 上的字母变成 字母表上 的前一个字母，而 s_{p+1} 则要变成 字母表上 的后一个字母。

你需要回答对于输入的单词，一共有多少种与它意思一致的单词。

另外，对于字母 a ，不能将它变成前一个字母（因为它在字母表上没有前一个字母），同理 字母 z 也不能变成后一个字母。

给出多个单词（字符串），你需要分别对它们做出回答，答案对 1e9+7 取模。

思路

不要被这冗长的题意吓到。

不妨将字符串的每一位视作数字，那么 a=1,b=2...z=26。定义转换后为第 i 位为 s_i，在这上面操作即可。

每一次操作相当于 s_i\pm 1,s_{i+1}\mp1。易发现：对于 \forall (i,j)，都有 s_i\pm1,s_j\mp1。这一点可以构造法验证。

于是可得到关键性质：对于两个长度相等的串 S、P，若有 \sum s_i=\sum p_i，那么经过若干次操作后两串可相互转换。

还是构造法，每次将操作 p_i 使得 p_i=s_i，又因为和不变，所以必定可以逐位确定 p_i，最终 P=S，反之同理。

于是不妨将 S 抽象为 sm=\sum s_i 个小球，其中有 sm-1 个空格、|s|-1 个板，每种板的不同插入方案都对应与 S 相等的字符串，统计插板方案数即可。

但是注意，每个板构成的区间的大小都必须在 [1,26] 之间，因此排列组合的插板法是不行的，考虑递推求解。

那么 f_{i,j} 表示前 i 个空插入 j 个隔板，且第 i 个空必有板时的方案数之和，那便有状态转移方程 f_{i,j}=\sum\limits_{k=i-26}^{i-1}f_{k,j-1}。

在查询之前递推即可，预处理时间复杂度是 O(26^2n^2)，每次查询只需 O(1)。

代码

递推代码如下，我怕少算就多循环了几遍，不影响结果。

f[0][0]=1;
for(int i=1; i<=3000;i++){
    for(int j=1; j<=min(j,1LL*105);j++){
        for(int k=max(1LL*0,i-26); k<=i-1;k++){
            f[i][j]=(f[i][j]+f[k][j-1])%mod;
        }
    }
}