問題一覧 > 通常問題

No.1645 AB's abs

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 214
作問者 : 蜜蜂 / テスター : Mitarushi ygussany
お気に入りにしたユーザー ProblemId : 6489 / 自分の提出
問題文最終更新日: 2021-08-01 20:44:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 309 (順位表) の他の問題:

Problem Statement

You are given a sequence $A$ consisting of $N$ positive integers $A_1,A_2,\dots,A_N$.
Also, for a sequence $B$ consisting of $N$ elements, each of which is either $1$ or $-1$, define $f(B)$ as follows.

  • $f(B)=|A_1 \times B_1 + A_2 \times B_2 + \dots + A_N \times B_N|$
  • There are $2^N$ possible sequences $B$. Find the sum of $f(B)$ over all of them, modulo $998244353$.

    Input

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

    • $1 \leq N \leq 100$
    • $1 \leq A_i \leq 100$ ( $1 \leq i \leq N$ )
    • All inputs are integers.

    Output

    Output the sum of $f(B)$ over all $2^N$ possible sequences $B$, modulo $998244353$, followed by a newline.

    Sample

    Sample 1
    Input
    2
    1 3
    Output
    12

    The $2^2=4$ possible sequences $B$ and their corresponding values of $f(B)$ are as follows.

    • When $B=(1,1)$, $f(B)=4$.
    • When $B=(1,-1)$, $f(B)=2$.
    • When $B=(-1,1)$, $f(B)=2$.
    • When $B=(-1,-1)$, $f(B)=4$.
    Their sum is $12$.

    Sample 2
    Input
    1
    1
    Output
    2

    Sample 3
    Input
    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
    Output
    225127881

    Output the remainder when divided by $998244353$.

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