問題一覧 > 通常問題

No.2717 Sum of Subarray of Subsequence

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 104
作問者 : ecottea / テスター : akakimidori 👑 hamamu
お気に入りにしたユーザー ProblemId : 10593 / 自分の提出
問題文最終更新日: 2024-03-25 19:33: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 426 (順位表) の他の問題:

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