問題一覧 > 通常問題

No.2111 Sum of Diff

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 175
作問者 : bayashiko / テスター : first_vil noimi
お気に入りにしたユーザー ProblemId : 8386 / 自分の提出
問題文最終更新日: 2022-10-28 04:48:09
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 366 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A=(a_1,a_2,\ldots,a_N)$ with $N$ elements.

There are $2^N-N-1$ (not necessarily contiguous) subsequences $A'=(a'_1,a'_2,\ldots,a'_k)$ of $A$ with at least $2$ elements in total, where subsequences that are equal as sequences but taken from different positions are distinguished.

Find the sum of the following value over all of them, modulo $998244353$.

  • $\displaystyle \sum_{j=1}^{k-1} (a'_j-a'_{j+1})$

Input

$N$
$a_1\ a_2\ \ldots\ a_N$

  • $2\le N\le 2×10^5$
  • $0\le a_i\le 998244352$
  • All inputs are integers.

Output

Output the answer.

Sample

Sample 1
Input
3
3 2 1
Output
6

The subsequences of $(3,2,1)$ with at least $2$ elements are the $4$ subsequences $(3,2),(3,1),(2,1),(3,2,1)$. The value of the expression for each of them is as follows.

  • $(3-2)=1$
  • $(3-1)=2$
  • $(2-1)=1$
  • $(3-2)+(2-1)=1+1=2$

Therefore, output $6$, the sum of these values.

Sample 2
Input
2
0 1
Output
998244352

$(0-1)=-1$, but note that you must output the remainder when divided by $998244353$.

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