問題一覧 > 通常問題

No.1645 AB's abs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 206
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi ygussanyygussany
5 ProblemId : 6489 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-01 20:44:11

問題文

$N$ 個の正整数 $A_1,A_2,\dots,A_N$ からなる数列 $A$ が与えられます。
また、 $N$ 個の $1$ か $-1$ のいずれかからなる数列 $B$ に対し、 $f(B)$ を以下のように定義します。

  • $f(B)=|A_1 \times B_1 + A_2 \times B_2 + \dots + A_N \times B_N|$

    • $B$ としてありえる数列は $2^N$ 通りありますが、その全てに対して $f(B)$ を足し合わせた値を $998244353$ で割った余りを求めてください。

    入力

    $N$
    $A_1\ \ A_2\ \ \cdots A_N$

    • $1 \leq N \leq 100$
    • $1 \leq A_i \leq 100$ ( $1 \leq i \leq N$ )
    • 入力は全て整数

    出力

    $2^N$ 通りある $B$ としてありえる数列全てに対して $f(B)$ を足し合わせた値を $998244353$ で割った余りを出力し、最後に改行してください。

    サンプル

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

    $2^2=4$ 通りありえる $B$ とそれに対応する $f(B)$ の値は以下の通りです。

    • $B=(1,1)$ のとき、 $f(B)=4$ です。
    • $B=(1,-1)$ のとき、 $f(B)=2$ です。
    • $B=(-1,1)$ のとき、 $f(B)=2$ です。
    • $B=(-1,-1)$ のとき、 $f(B)=4$ です。
    これらの和は $12$ です。

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

    サンプル3
    入力
    30
    22 89 88 33 99 38 1 79 93 15 65 62 74 59 4 21 4 70 20 85 38 5 10 30 96 56 89 42 6 81
    出力
    225127881

    $998244353$ で割った余りを出力してください。

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