No.2717 Sum of Subarray of Subsequence
タグ : / 解いたユーザー数 104
作問者 :
akakimidori
👑
hamamu
Problem Statement
You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$. For every non-empty (not necessarily contiguous) subsequence $B$ of $A$, solve Problem 1 below, and find the sum of the answers:
-
Problem 1: For every non-empty contiguous subarray $C$ of the sequence $B$, solve Problem 2 below, and find the sum of the answers:
- Problem 2: Find the sum of the elements of the sequence $C$.
Since the answer can be very large, output the answer modulo $998244353$.
Note that, for both subsequences and contiguous subarrays, two choices are distinguished if the sets of indices of the chosen elements differ, even if they are equal as sequences.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 998244353$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $A_1 \ \ldots \ A_N$
Output
Output the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
50
The non-empty subsequences of $A = (1, 2, 3)$ are $(1, 2, 3), (1, 2), (1, 3), (2, 3), (1), (2), (3)$.
Let us find the answer to Problem 1 for $(1, 2, 3)$. The non-empty contiguous subarrays of $(1, 2, 3)$ are $(1, 2, 3), (1, 2), (2, 3), (1), (2), (3)$, and adding up the answers to Problem 2 for each of them gives $6 + 3 + 5 + 1 + 2 + 3 = 20$.
Finding the answers to Problem 1 for each of the remaining $(1, 2), (1, 3), (2, 3), (1), (2), (3)$ in the same way gives $6, 8, 10, 1, 2, 3$, so the answer is $20 + 6 + 8 + 10 + 1 + 2 + 3 = 50$.
Sample 2
Input
2 777777777 777777777
Output
673689250
Output the answer modulo $998244353$.
Sample 3
Input
10 3 1 4 1 5 9 2 6 5 3
Output
176640
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。