No.2633 Subsequence Combination Score
問題文最終更新日: 2024-02-16 00:24:26
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2