problem
给定一个由小写字符构成的字符串 \(S\)。
令一个字符串的价值为该串的本质不同非空子序列个数，其中子序列可以为整体。
求 \(S\) 所有子序列的价值和。答案对 \(10^9+7\) 取模。
对于 \(100\%\) 的数据，\(1\le |S|\le 10^6\)。
solution
考虑如何求出一个字符串的价值？
令 \(f_i\) 表示以字符 \(i\) 为结尾有多少个本质不同的非空子序列。
增量法，每次加入字符 \(r\)，将 \(f_r\) 修改为 \(1+\sum_{i}f_i\)，表示将之前所有以 \(r\) 为结尾的子序列都接上 \(r\)，最后补上单独的 \(r\)。
我们可以将这样的过程表示为矩阵：（假设只有 \(3\) 个字符，加入字符 \(1\)）
\[\begin{bmatrix} f_0 &f_1 &f_2 &1 \end{bmatrix}\times \begin{bmatrix} 1 &1 &0 &0\\ 0 &1 &0 &0\\ 0 &1 &1 &0\\ 0 &1 &0 &1 \end{bmatrix}= \begin{bmatrix} f'_0 &f'_1 &f'_2 &1 \end{bmatrix}. \]回到原问题，要求所有子序列的价值之和。我们考虑用二项式展开的集合意义：
标签：字符,begin,06,Distinct,题解,字符串,bmatrix,序列,end From： https://www.cnblogs.com/caijianhong/p/solution-P7888.html