题解：AT_arc106_d [ARC106D] Powers

_1RR0R · 2026-08-07 21:53:03 · 题解

从容斥角度的逐步推导题解。

令答案为 F(x)=\sum\limits_{L=1}^{N-1}\sum\limits_{R=L+1}^{N}(A_L+A_R)^{x}。

先容斥，令 G(x)=\sum\limits_{L=1}^{N}\sum\limits_{R=1}^{N}(A_L+A_R)^{x}。

考虑 G 中的每一对各出现了几次：

• 若挑到两个不同的数 i \neq j，则会将 (L,R) 计算 2 次。
• 若挑到两个相同的数 i = j，则只会算 1 次。

所以 G(x)=2\times F(x)+\sum\limits_{i=1}^{N}(2A_i)^x。

那么 F(x)=\frac{G(x)-\sum\limits_{i=1}^{N}(2A_i)^x}{2}。

用二项式定理拆开：G(x)=\sum\limits_{L=1}^{N}\sum\limits_{R=1}^{N}\sum\limits_{k=0}^{x}\binom{x}{k}A_L^k A_R^{x-k}，交换求和顺序 (G(x)=\sum\limits_{k=0}^{x}\binom{x}{k})(\sum\limits_{L=1}^{N}A_L^k)(\sum\limits_{R=1}^{N}A_R^{x-k})。现在 L 和 R 就被分开了。

注意到 k 比较小，考虑预处理出 S_k=\sum\limits_{i=1}^{N}A_i^k。

最后的式子就是：

直接求就行了，复杂度 \mathcal{O}(nk)。