No.2111 Sum of Diff
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
bayashiko