专栏文章

题解：AT_abc214_f [ABC214F] Substrings

eendswitch
AT_abc214_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlps74
此快照首次捕获于
2025/12/02 04:28
3 个月前
此快照最后确认于
2025/12/02 04:28
3 个月前
查看原文
设 dpi,cdp_{i, c} 表示前 ii 位以字符 cc 为结尾的方案数。
有转移：
dpi,c=dpi−1,c (si≠c)dp_{i, c} = dp_{i - 1, c} \ (s_i \not = c) dpi,c=∑k=1Σdpi−2,k (si=c)dp_{i, c} = \sum_{k = 1} ^ \Sigma dp_{i - 2, k} \ (s_i = c)
其中 Σ\Sigma 为字符集。
根据实现时间复杂度为 O(nΣ)O(n \Sigma) 或者 O(nΣ2)O(n \Sigma ^ 2)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...