大意: 定义$f(a)$表示序列$a$本质不同子序列个数. 给定$n,m$, 求所有长$n$元素范围$[1,m]$的序列的$f$值之和.
显然长度相同的子序列贡献是相同的.
不考虑空串, 假设长$x$, 枚举第一次出现位置, 可以得到贡献为$\sum\limits_{i=x}^n\binom{i-1}{x-1}(m-1)^{i-x}m^{n-i}$
总的答案就为$\sum\limits_{x=1}^n m^x \sum\limits_{i=x}^n\binom{i-1}{x-1}(m-1)^{i-x}m^{n-i}$
化简一下即可O(1)求出
Different Subsets For All Tuples CodeForces - 660E (组合计数)
原文：https://www.cnblogs.com/uid001/p/11663918.html