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\)。
code
Submission #228232951 - Codeforces
标签:正整数,值域,sum,CF660E,序列,长度 From: https://www.cnblogs.com/FreshOrange/p/17765459.html