P7509 Tear and Erase.

Why tear, and why erase?

Given an integer sequence $a_1,a_2,\dots,a_n$ of length $n$, and a rational sequence $p_1,p_2,\dots,p_n$. At each position there is a random coefficient $c_i \in \{0,1\}$, where $P(c_i = 1) = p_i$ and $P(c_i = 0) = 1 - p_i$. Note that when writing the random coefficients as a sequence, it can be divided into several maximal consecutive segments of $0$ and $1$. “Maximal” means it cannot be extended to either side. Define the value (weight) of a coefficient sequence as follows: if the coefficient sequence has exactly $k$ maximal consecutive segments of $1$, then its value is $\sum\limits_{i=1}^n c_i a_i$; otherwise, its value is $0$. Find the expected value of this coefficient sequence. Output the answer modulo $998244353$.

The first line contains two positive integers $n,k$. The second line contains $n$ non-negative integers $a_1,a_2,\dots,a_n$. The third line contains $n$ non-negative integers $p_1,p_2,\dots,p_n$, given modulo $998244353$.

One line with one non-negative integer, representing the expectation.

**Sample Explanation** For the first sample, $c_i$ must be $1$, and there must be exactly $1$ maximal consecutive segment, so the value must be $1 + 2 + 3 + 4 + 5 = 15$. For the second sample, the value is non-zero only when $c_1 = 1,c_2 = 0,c_3 = 1$, and the probability of this case is $\frac 12 \times \frac 12 \times \frac 12 = \frac 18$, so the expectation is $\frac{1+3}8 = \frac 12 \equiv 499122177 \pmod {998244353}$. **Constraints** For $30\%$ of the testdata, $n \le 20$. For $60\%$ of the testdata, $n \le 10^3$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le \min\left(20,\left\lfloor\frac{n+1}2\right\rfloor\right)$, $0 \le a_i,p_i < 998244353$. Translated by ChatGPT 5