问题描述

塔子哥最近在研究字符串的子序列问题。给定一个仅由小写字母组成、长度为 $n$ 的字符串 $s$，该字符串有 $2^n - 1$ 个非空子序列。塔子哥希望你能帮他计算所有子序列中不同字符的个数总和。由于答案可能非常大，你需要输出对 $10^9 + 7$ 取模后的结果。

题解

贡献法计数

对于一个长度为 $n$ 的字符串 $|S|$，记字符 $c$ 出现的次数为 $cnt[c]$，那么对答案的贡献为 $(2 ^ {cnt[c]} - 1) \cdot (2 ^ {n - cnt[c]})$，即当前字符最少选一个，其他字符任意选，最终将答案累加即可。

AC代码

Python