1 条题解

  • 0
    @ 2026-11-15 13:02:15

    题目分析

    题意中的规则比较绕,我们先从简单情况入手分析。

    对于长度为 22 的连续子串,只要两个字符不同就满足要求;对于长度为 33 的子串,要求三个字符互不相同。当考虑长度大于 33 的连续子串时可以发现:只要它内部不存在长度为 33 的不合法子串,那么整个子串一定合法。例如 abaca 是不合法的,那么它内部必然存在长度为 33 的不合法子串 aba。

    有了上述性质,限制就只与每个位置相邻的两个字符有关,可以尝试用动态规划解决。

    设 fi,j,kf_{i,j,k} 表示考虑到前 ii 个字符,第 i−1i-1 个字符为 jj、第 ii 个字符为 kk,且前 ii 个字符构成的串合法的方案数。转移时枚举下一个字符 ll,只要保证 ll 与 jj、kk 都不同即可,即:

    $$f_{i+1,k,l} \mathrel{+}= f_{i,j,k}\quad (l \neq j,\ l \neq k)$$

    转移时还要注意原串第 ii 位若是字母则只能取该字母,若是 ? 则 26 个字母都可以取。初始状态 f0,0,0=1f_{0,0,0}=1(用 00 表示空),最终答案即为所有 fn,j,kf_{n,j,k} 之和。

    由于 n≤5000n \le 5000,状态数约为 n×27×27n \times 27 \times 27,转移枚举 ll 后总体复杂度为 O(26n⋅26⋅26)O(26 n \cdot 26 \cdot 26),可以接受。答案需要对 998244353998244353 取模。

    • 1

    信息

    ID
    46
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者