Sum of Averages (subset)

$A$の各要素が答えにどれだけ寄与するかを考えます。$A$のある要素$A_i$と$k = 1,2,\cdots,N$について、$A_i$が大きさ$k$の部分集合に含まれる方法の数は$A_i$以外の$N - 1$要素の中から異なる$k-1$要素をとってくる方法の数に等しく、$\binom {N-1}{k-1}$通りです。したがって$A_i$の答えに対する寄与は$A_i \sum_{k = 1}^N \frac{\binom {N-1}{k-1}}{k}$となります。 ここで、$\frac{\binom {N-1}{k-1}}{k} = \frac{(N- 1)!}{(N-k)!k!} = \frac{N!}{(N-k)!k!N} = \frac{\binom{N}{k}}{N}$なので、 $\sum_{k = 1}^N\frac{\binom {N-1}{k-1}}{k} = \sum_{k = 1}^N\frac{\binom{N}{k}}{N} = \frac{1}{N}((1 + 1)^N - \binom{N}{0}) = \frac{2^N-1}{N}$が成り立ちます。したがって答えは$\frac{2^N-1}{N}\sum_{i = 1}^N A_i$と求まります。よって$mod = 998244353$としてこの問題を時間計算量$O(N + \log mod)$で解くことができました。