题解：P12405 「CZOI-R3」星光闪耀

看到奇怪的限制 $\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$ 为当前轮的星团总数。

$\sum k^{a_{i}}$ 是前一轮的答案，可以直接得到。$c$ 的计算同样比较简单，设当前为第 $x$ 轮（最初为第 $1$ 轮），那么 $c=\binom{n+x-1}{x}$。考虑证明。我们把序列倒过来，即 $k^{n}$ 的出现次数在前面，$k^{1}$ 的在后面，那么有第 $i$ 轮的第 $j$ 个位置为 $\binom{i+j-2}{j-1}$，就有 $c=\sum\limits_{i=1}^{n} \binom{x+i-2}{i-1}=\sum\limits_{i=0}^{n-1} \binom{x+i-1}{i}=\sum\limits_{i=0}^{n-1} \binom{x+i-1}{x-1}=\binom{n+x-1}{x}$，最后一步是组合恒等式。

注意 $k\leq 1$ 要特判，而且不要忘了加上前一轮的答案。

时间复杂度 $\mathcal{O}(\sum m)$。