RT，想到了一个做法是求每一个 $i^k$ 对答案的贡献，化简之后得到了： $\sum_{i=1}^{n-1}i^k \times 2^{-i}$ 然后问了 U群，EI 说可以做到 $O(k+\log n)$，但是没说怎么做。。。

求问一下这个柿子怎么做到 $O(k+\log n)$