問題一覧 > 通常問題

No.2633 Subsequence Combination Score

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : 👑 potato167 / テスター : ebi_fly noya2
お気に入りにしたユーザー ProblemId : 10015 / 自分の提出
問題文最終更新日: 2024-02-16 00:24:26
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
traP 作問ハッカソンコンテスト 002(day1) (順位表) の他の問題:

Problem Statement

You are given a non-increasing sequence $A=(A_{1},A_{2},...,A_{N})$ of length $N$.

For a non-empty sequence $B$ of length $L$, its score $f(B)$ is defined as follows.

  • If $L=1$, then $f(B)=1$.
  • If $L\neq 1$, then $\displaystyle f(B)=\prod_{i=2}^{L}\binom{B_{i-1}}{B_{i}}$.

There are $2^{N}-1$ non-empty subsequences $A'$ of $A$. Find the sum of $f(A')$ over all of these $A'$, modulo $998244353$.

Here, $\displaystyle\binom{B_{i-1}}{B_{i}}$ is the number of ways to choose exactly $B_{i}$ items from $B_{i-1}$ distinguishable items, that is, the binomial coefficient.

Constraints

  • $1\leq N \leq 10^{5}$
  • $10^{5}\geq A_{1}$
  • $A_{i}\geq A_{i+1} \ (2\leq i\leq N)$
  • $A_{N}\geq 0$
  • All inputs are integers.

Input

$N$
$ A_1 \; A_2 \; ...\;A_N$

Output

Output the answer. Print a newline at the end.

Sample

Sample 1
Input
4
6 4 3 2
Output
469

For example, when $A'=(6,4,3)$, we have $f(A')=\displaystyle \binom{6}{4}\displaystyle \binom{4}{3}=60$.

Sample 2
Input
2
924 167
Output
793971661
Sample 3
Input
12
99740 98332 88628 81080 76561 68844 62493 52907 46058 40949 22847 854
Output
31340893

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