1 条题解
-
0
题目分析
题意中的规则比较绕,我们先从简单情况入手分析。
对于长度为 的连续子串,只要两个字符不同就满足要求;对于长度为 的子串,要求三个字符互不相同。当考虑长度大于 的连续子串时可以发现:只要它内部不存在长度为 的不合法子串,那么整个子串一定合法。例如
abaca是不合法的,那么它内部必然存在长度为 的不合法子串aba。有了上述性质,限制就只与每个位置相邻的两个字符有关,可以尝试用动态规划解决。
设 表示考虑到前 个字符,第 个字符为 、第 个字符为 ,且前 个字符构成的串合法的方案数。转移时枚举下一个字符 ,只要保证 与 、 都不同即可,即:
$$f_{i+1,k,l} \mathrel{+}= f_{i,j,k}\quad (l \neq j,\ l \neq k)$$转移时还要注意原串第 位若是字母则只能取该字母,若是
?则 26 个字母都可以取。初始状态 (用 表示空),最终答案即为所有 之和。由于 ,状态数约为 ,转移枚举 后总体复杂度为 ,可以接受。答案需要对 取模。
- 1
信息
- ID
- 46
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者