description
给定 \(n,m\)。 求所有长度为 \(n\)，值域是 \([1,m]\) 中的正整数的序列的本质不同子序列数量和。
\(n,m\leq 10^6\)
solution
考虑计算每个长度不超过 \(n\) ，值域为 \([1,m]\) 中的正整数的序列是多少个长度为 \(n\)，值域为 \([1,m]\) 中的正整数的序列的子序列。
问题和 CF1838E 几乎一样， 如何计数见我的这篇博客。
结论就是答案（不包含空子序列）为 \(\sum\limits_{i=1}^n m^i\sum\limits_{j=1}^{n-i}\dbinom{m}{j}(m-1)^j\)，前缀和一下计算即可。
每个长度为 \(n\)，值域为 \([1,m]\) 中的正整数的序列都含有空子序列，答案再加上一个 \(m^n\)。