No.2817 Competition
タグ : / 解いたユーザー数 37
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
ストーリー
必ずしもこの項を読む必要はない.
何らかの大会のチーム分けの場面を考えましょう.
チームの強さを単純にそのチームに属する人の強さの合計とします.すると,チーム数が同じであれば全チームの強さの総積が大きいほど偏りが少ないと考えることができます.
そのような計算をすべてのチーム分けに対して行うことを考えてみましょう.
問題文
長さ $N$ の数列 $A$ が与えられます. 以下を満たす正整数の集合の集合 $S$ を「良いグループの分け方」と呼ぶことにします.
このとき,良いグループの分け方 $S$ すべてについて以下の値を求め,その値の総和を求めてください.ただし答えは非常に大きくなりうるので $998244353$ で割った余りを出力してください.
制約
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq A_{i} \leq 10^{18}$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる.$N$ $A_{1}~~~A_{2} ~~\ldots ~~A_{N}$
出力
答えを出力せよ.
サンプル
サンプル1
入力
3 1 2 3
出力
34
$S=\{\{1\},\{2,3\}\},\{\{2\},\{1,3\}\},\{\{3\},\{1,2\}\},\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$ です.値の総和は $1\times(2+3)+2\times(1+3)+3\times(1+2)+1\times2\times3+(1+2+3)=34$ になります.
サンプル2
入力
1 1
出力
1
サンプル3
入力
5 1 1 1 1 1
出力
196
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。