問題一覧 > 通常問題

No.2062 Sum of Subset mod 999630629

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : nok0nok0 👑 ygussanyygussany
3 ProblemId : 8361 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-25 22:27:26

問題文

競プロで有名な素数といえば $998244353$ ですが、実は $999630629$ も素数です。 問題文中にこの $2$ つの素数が出てくるので注意してください。

長さ $N$ の整数列 $A$ が与えられます。また $ \lbrace 1,2, \dots , N \rbrace$ の空でない部分集合 $S$ に対して $f(S)$ を次のように定めます。

 $f(S)= \left( \displaystyle \sum_{i \in S} A_i \right )\ \mathrm{mod} \ 999630629$

$\lbrace 1,2,\dots , N \rbrace$ の空でない部分集合 $S$ は $2^N-1$ 個ありますが、その全てに対して $f(S)$ を求め、その総和を $998244353$ で割った余りを求めてください。

(答えも $999630629$ で割るのではないことに注意してください。)

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^4$
  • 入力は全て整数
  • 出力

    $f(S)$ の総和を $998244353$ で割った余りを求めてください。

    サンプル

    サンプル1
    入力
    2
    3 5
    出力
    16


    $(A_1) \ \mathrm{mod} \ 999630629=3$
    $(A_2) \ \mathrm{mod} \ 999630629=5$
    $(A_1+A_2) \ \mathrm{mod} \ 999630629=8$
    よって求める答えは $3+5+8=16$ となります。

    サンプル2
    入力
    1
    1 
    出力
    1

    サンプル3
    入力
    6
    1 2 3 4 5 6
    出力
    672

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。