問題一覧 > 通常問題

No.2817 Competition

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : highlighter / テスター : Magentor hirayuu_yc Yoyoyo8128 zeta7532 warabi0906
ProblemId : 10940 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-19 21:19:51

ストーリー

必ずしもこの項を読む必要はない．

何らかの大会のチーム分けの場面を考えましょう．

チームの強さを単純にそのチームに属する人の強さの合計とします．すると，チーム数が同じであれば全チームの強さの総積が大きいほど偏りが少ないと考えることができます．

そのような計算をすべてのチーム分けに対して行うことを考えてみましょう．

問題文

長さ $N$ の数列 $A$ が与えられます． 以下を満たす正整数の集合の集合 $S$ を「良いグループの分け方」と呼ぶことにします．

  • 任意の $S$ の要素 $T$ について， $\lvert T \rvert \geq 1$
  • $\displaystyle\sum_{T \in S} \lvert T \rvert = N$
  • 任意の $S$ の相異なる要素 $T,U$ について， $T \cap U=\varnothing$
  • すべての $1$ 以上 $N$ 以下の整数 $i$ について，ある $T \in S$ が存在して， $i \in T$

    • このとき，良いグループの分け方 $S$ すべてについて以下の値を求め，その値の総和を求めてください．ただし答えは非常に大きくなりうるので $998244353$ で割った余りを出力してください．

  • $\displaystyle\prod_{T \in S} \displaystyle\sum_{i \in T} A_{i}$

    • 制約

    • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。