会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
考虑每个字母对答案的贡献，而不是枚举子序列。
对某个字母 c，记它在 s 中出现 r 次。一个子序列会让 c 计入种类数，当且仅当该子序列至少选出一个 c。此时：
- c 的 r 个出现位置不能全不选，有 2r−1 种选法；
- 其余 n−r 个位置可任意选或不选，有 2n−r 种选法。
题目内容
乐谱上有一段由小写英文字母组成的旋律 s，长度为 n。可以从中选出若干个位置，并保持它们在原旋律中的相对顺序，得到一个非空子序列。
一个子序列的种类数定义为其中出现过的不同字母个数。例如子序列 abac 中出现了 a、b、c，种类数为 3。
