No.1239 Multiplication -2
eSeF
りあん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. Show the original
Problem Statement
You are given an integer sequence $a$ of length $N$. There are $2^{N-1}$ ways to split it into $1$ or more non-empty contiguous subsequences. When $1$ of these ways is chosen at random, find the expected value of "the number of resulting subsequences whose product of all elements is $-2$".
It can be shown that the answer can be expressed as a rational number $\dfrac{P}{Q}\ (Q\neq 0)$. Output its representation in $\bmod 998244353$, that is, the integer $E$ satisfying $E\times Q\equiv P\ \pmod{998244353}$ and $0\le E\lt 998244353$.
Input
$N$ $a_1\ \cdots \ a_N$【Constraints】
- $1\le N\le 2\times 10^5$
- $|a_i|\le 2$
- All input values are integers.
Output
Output the expected value in $\bmod 998244353$.
Sample
Sample 1
Input
3 -2 1 -2
Output
499122178
There are $4$ ways to split, which are as follows:
- $\{ -2,1,-2\}$
- $\{ -2\},\ \{ 1,-2\}$
- $\{ -2,1\} ,\ \{ -2\}$
- $\{ -2\} ,\ \{ 1\} ,\ \{ -2\}$
The numbers of subsequences whose product of all elements is $-2$ are $0$, $2$, $2$, and $2$, respectively. Since these are chosen with equal probability, the expected value is $\dfrac{3}{2}$.
Since $499122178\times 2\equiv 3\ \pmod{998244353}$, output $499122178$.Sample 2
Input
4 -1 -1 0 2
Output
0
No matter how the sequence is split, there is no subsequence whose product is $-2$. Therefore, the expected value is $0$.
Sample 3
Input
8 0 -2 0 -2 0 -2 -1 -1
Output
124780545
The expected value is $\dfrac{7}{8}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。