Limits
1s, 512 MB

*It is Argentina vs France in the football world cup final of 2022 in a parallel universe.*

You are a supporter of Argentina. 120 minutes of play has ended in a draw. So, penalty shootout will begin. You know the scoring probabilities for each of the 22 players on the field. You also know that both teams would send shooters in an optimal order. And the order must be submitted to the referee **before** the shootout begins. Argentina start first. The rules of penalty shootout are as follows:

Teams take shots alternately.

For any consecutive 11 shots of a team, a player can shoot exactly once.

If both teams have taken equal number of shots and each team has taken at least 5 shots, then the leading team wins. If scores are still tied, they continue shooting until a team wins.

We denote a goal with $\checkmark$ and a miss with $\times$.

The shootout begins. The scorecard after 5 shots per team is:

ARG: $\checkmark$$\checkmark$$\checkmark$$\times$$\checkmark$

FRA: $\times$$\checkmark$$\checkmark$$\checkmark$$\checkmark$

This means Argentina missed its 4th shot and France missed its 1st shot. The score is tied at 4-4.

You are losing your sanity from the suspense. You know the first 5 shooters went in optimal order which was submitted before the shootout began. Now you calculate the probability of Argentina winning the world cup. This means you calculate it **after** 5 shots per team was taken and before Argentina’s 6th shot. Print the number modulo $998244353$.

Formally, let the probability be an irreducible fraction $\frac{x}{y}$. Print the value $x \cdot y^{-1}$mod $998244353$. Where $y^{-1}$ is an integer such that $y \cdot y^{-1} \equiv 1$ mod $998244353$. Input data for this problem was made such that $y^{-1}$ exists.

A player might need to take multiple shots in the shootout. The outcome of any shot **does not change** his scoring probability.

**Examples:**

Some possible outcomes of the shootout continuing from the current situation:

ARG: $\checkmark$$\checkmark$$\checkmark$$\times$$\checkmark$$\times$

FRA: $\times$$\checkmark$$\checkmark$$\checkmark$$\checkmark$$\checkmark$

After 6 shots per team, France lead. So France wins.

ARG: $\checkmark$$\checkmark$$\checkmark$$\times$$\checkmark$ $\checkmark$ $\checkmark$ $\times$$\checkmark$

FRA: $\times$$\checkmark$$\checkmark$$\checkmark$$\checkmark$ $\checkmark$ $\checkmark$ $\times$ $\times$

After 9 shots per team, Argentina lead by 7-6. So Argentina wins.

ARG: $\checkmark$$\checkmark$$\checkmark$$\times$$\checkmark$$\times$ $\times$$\times$ $\checkmark$ $\checkmark$$\checkmark$$\times$$\times$$\checkmark$$\times$$\times$ $\checkmark$ $\checkmark$$\checkmark$$\times$$\times$$\checkmark$$\checkmark$ $\checkmark$

FRA: $\times$$\checkmark$$\checkmark$$\checkmark$$\checkmark$ $\times$ $\times$ $\times$$\checkmark$$\checkmark$ $\checkmark$$\times$$\times$$\checkmark$$\times$$\times$ $\checkmark$ $\checkmark$$\checkmark$$\times$$\times$$\checkmark$$\checkmark$$\times$

After 24 shots per team, Argentina lead by 14-13. So Argentina wins.

The input consists of $2$ lines, each containing $11$ space separated integers.

The $i$-th integer $A_i (1 \leq A_i \lt 100)$ on the first line indicates that scoring probability for the $i$-th player of Argentina is $\frac{A_i}{100}$.

The $i$-th integer $F_i (1 \leq F_i \lt 100)$ on the second line indicates that scoring probability for the $i$-th player of France is $\frac{F_i}{100}$.

Input is **not** necessarily given in the optimal shooting order.

Print a single integer, the probability of Argentina winning modulo $998244353$.

Input | Output |
---|---|

99 99 99 99 99 99 99 99 99 99 99 1 1 1 1 1 1 1 1 1 1 1 | 403188064 |

The actual probability is $\frac{9801}{9802}$. |

Input | Output |
---|---|

41 49 94 58 69 65 98 57 39 7 71 85 5 4 90 8 46 21 75 84 41 93 | 471266917 |

The actual probability is $\frac{8055795054746322203650663244113381}{12123531088532242843736676673393538}$. Which is roughly equal to $0.6644759679270646$. |

Input | Output |
---|---|

50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 | 499122177 |

The probability is $\frac{1}{2}$. |

Login to submit.

0%
Solution Ratio

Toph uses cookies. By continuing you agree to our Cookie Policy.