题解：AT_abc214_f [ABC214F] Substrings
endswitch
·
·
题解
设 dp_{i, c} 表示前 i 位以字符 c 为结尾的方案数。
有转移：
dp_{i, c} = dp_{i - 1, c} \ (s_i \not = c)
dp_{i, c} = \sum_{k = 1} ^ \Sigma dp_{i - 2, k} \ (s_i = c)
其中 \Sigma 为字符集。
根据实现时间复杂度为 O(n \Sigma) 或者 O(n \Sigma ^ 2)。