AtCoder Regular Contest 116
翻译中…
Problem Statement
翻译中…
Given is a sequence $A$ of $N$ integers. There are $2^N - 1$ non-empty subsequences $B$ of $A$. Find the sum of $\max\left(B\right) \times \min\left(B\right)$ over all of them.
翻译中…
Since the answer can be enormous, report it modulo $998244353$.
翻译中…
Constraints
翻译中…
- All values in input are integers.
$1 \leq N \leq 2 \times 10^5$$0 \leq A_i \leq 998244352$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
A_1 A_2 \cdots A_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
3
2 4 3
Output #1
63
There are $7$ subsequences $B$, as follows:
- $B = \left(2\right)$ : $\max\left(B\right) \times \min\left(B\right) = 4$
- $B = \left(4\right)$ : $\max\left(B\right) \times \min\left(B\right) = 16$
- $B = \left(3\right)$ : $\max\left(B\right) \times \min\left(B\right) = 9$
- $B = \left(2, 4\right)$ : $\max\left(B\right) \times \min\left(B\right) = 8$
- $B = \left(2, 3\right)$ : $\max\left(B\right) \times \min\left(B\right) = 6$
- $B = \left(4, 3\right)$ : $\max\left(B\right) \times \min\left(B\right) = 12$
- $B = \left(2, 4, 3\right)$ : $\max\left(B\right) \times \min\left(B\right) = 8$
The answer is the sum of them: $63$.
Input #2
1
10
Output #2
100
Input #3
7
853983 14095 543053 143209 4324 524361 45154
Output #3
206521341
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。