P5326 [ZJOI2019] Switches

Jiutiao Keliang is a playful girl. One day, she and her good friend Brother Fahai went to play an escape room. In front of them are $n$ switches, and at the beginning every switch is in the off state. To pass this level, the switches must reach a specified state. The target state is given by a binary array $s$ of length $n$. $s_i = 0$ means the $i$-th switch needs to be off in the end, and $s_i = 1$ means the $i$-th switch needs to be on in the end. However, as challengers, Keliang and Fahai do not know $s$. So they decided to use a safer method: pressing randomly. Based on the shape and position of the switches, they used some “mystic” methods to assign each switch a weight $p_i$ ($p_i > 0$). Each time, they choose and press one switch with probability proportional to $p_i$ (the probability that the $i$-th switch is chosen is $\frac{p_i}{\sum^n_{j=1}p_j}$). After a switch is pressed, its state is flipped: on becomes off, and off becomes on. **Note that each round of selection is completely independent.** During the process of pressing switches, once the current states of switches match $s$, the door in front of Keliang and Fahai will open. They will immediately stop pressing switches and move on to the next level. As a very lucky person, Keliang opened the door after pressing $\sum^n_{i=1} s_i$ times. To feel how good her luck was, she wants you to help her compute: using this random pressing method, what is the expected number of presses needed to pass this level?

The first line contains an integer $n$, representing the number of switches. The second line contains $n$ integers $s_i$ ($s_i\in \{0,1\}$), representing the target state of each switch. The third line contains $n$ integers $p_i$, representing the weight of each switch.

Output one line with one integer, representing the answer modulo $998244353$. That is, if the answer in simplest fractional form is $\frac{x}{y}$ ($x \ge 0$, $y \ge 1$, $\gcd(x, y) = 1$), you should output $x \times y^{-1} \bmod 998244353$.

**[Sample Explanation \#1]** In the first two presses, there is a probability of $\frac12$ to reach $s$, and a probability of $\frac12$ to return to the initial state. Therefore, the expected number of switch presses is: $$\sum^{+\infty}_{i=1}2i\times \left(\frac12\right)^i=4$$ --- **[Constraints and Notes]** | Test Point | $n$ | Other Notes | Test Point | $n$ | Other Notes | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $=2$ | None | $6$ | $\le 100$ | $p_i\le 2,s_i=1$ | | $2$ | $=2$ | None | $7$ | $\le 100$ | $p_i\le 2,s_i=1$ | | $3$ | $\le 8$ | None | $8$ | $\le 100$ | $\sum p_i\le 2\times 10^3$ | | $4$ | $\le 8$ | None | $9$ | $\le 100$ | $\sum p_i\le 2\times 10^3$ | | $5$ | $\le 100$ | $p_i=1$ | $10$ | $\le 100$ | None | For $100\%$ of the testdata, it is guaranteed that $n\ge1$, $\sum^n_{i=1}p_i\le5\times10^4$, and $p_i\ge1$. Translated by ChatGPT 5