题解：P12405 「CZOI-R3」星光闪耀
Monomial
·
·
题解
看到奇怪的限制 \sum m \leq 2 \times 10^{7}，考虑从这上面入手。
我们考虑一轮中的 k^{v} 会对下一轮产生什么贡献，其应当是 k^{v-1},k^{v-2},\dots,k^{2},k^{1}。这个是等比数列的形式，只是缺掉了 k^{0}。
那么，k^{v} 对下一轮的贡献就是 \frac{k^{v}-1}{k-1}-1，总贡献是 -c+\sum \frac{k^{a_{i}}-1}{k-1}，\frac{1}{k-1} 提出来得到 -c+\frac{1}{k-1} \sum k^{a_{i}}-1，也就是 -c+\frac{1}{k-1} ((\sum k^{a_{i}})-c)，其中 c 为当前轮的星团总数。
注意 $k\leq 1$ 要特判，而且不要忘了加上前一轮的答案。
时间复杂度 $\mathcal{O}(\sum m)$。