{"raw_statement":[{"iden":"statement","content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of contests and friends.  \nLet $ P, Q \\in \\mathbb{Z} $ such that $ p = \\frac{P}{10^6} $, $ q = \\frac{Q}{10^6} $, and $ r = 1 - p - q $.  \nLet $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\mathbb{Z}^+ $ be the set of distinct desired T-shirt sizes.  \n\nFor each $ a_i \\in A $, define the random variable $ X_i $ indicating whether a T-shirt of size $ a_i $ is received:  \n$$\nX_i = \\begin{cases}\n1 & \\text{if at least one T-shirt of size } a_i \\text{ is received}, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 2 \\cdot 10^5 $  \n2. $ 0 \\le P, Q \\le 10^6 $, $ P + Q \\le 10^6 $  \n3. $ 1 \\le a_i \\le 10^9 $, all $ a_i $ distinct  \n\n**Objective**  \nCompute the expected number of friends who receive a T-shirt:  \n$$\n\\mathbb{E}\\left[\\sum_{i=1}^n X_i\\right] = \\sum_{i=1}^n \\mathbb{P}(X_i = 1)\n$$\n\nFor each $ a_i $, define the set of sizes that can produce a T-shirt of size $ a_i $:  \n$$\nS_i = \\{a_i - 1, a_i, a_i + 1\\}\n$$\n\nLet $ C_j $ be the event that T-shirt size $ j $ is *requested* (i.e., $ j \\in A $).  \nThen the probability that size $ a_i $ is received is:  \n$$\n\\mathbb{P}(X_i = 1) = 1 - \\prod_{j \\in S_i \\cap A} \\left(1 - \\mathbb{P}(\\text{size } j \\text{ is chosen and yields } a_i)\\right)\n$$\n\nBut more precisely:  \nFor each requested size $ a_i $, the T-shirt of size $ a_i $ can be obtained from:  \n- Registering for $ a_i $: yields $ a_i $ with prob $ r $, $ a_i - 1 $ with prob $ p $, $ a_i + 1 $ with prob $ q $  \n- Registering for $ a_i - 1 $: yields $ a_i $ with prob $ q $  \n- Registering for $ a_i + 1 $: yields $ a_i $ with prob $ p $  \n\nThus, the probability that **no** T-shirt of size $ a_i $ is received is:  \n$$\n\\prod_{\\substack{k \\in A \\\\ k \\in \\{a_i - 1, a_i, a_i + 1\\}}} \\left(1 - \\text{prob that registering for } k \\text{ produces } a_i\\right)\n$$\n\nLet $ N_i = \\{ k \\in A \\mid k \\in \\{a_i - 1, a_i, a_i + 1\\} \\} $  \nThen:  \n$$\n\\mathbb{P}(X_i = 0) = \\prod_{k \\in N_i} \\left(1 - \\begin{cases}\nr & \\text{if } k = a_i \\\\\nq & \\text{if } k = a_i - 1 \\\\\np & \\text{if } k = a_i + 1\n\\end{cases}\\right)\n$$\n\nSo:  \n$$\n\\mathbb{P}(X_i = 1) = 1 - \\prod_{k \\in N_i} \\left(1 - c_{k,i}\\right)\n$$  \nwhere $ c_{k,i} = \\begin{cases}\nr & k = a_i \\\\\nq & k = a_i - 1 \\\\\np & k = a_i + 1\n\\end{cases} $\n\nFinally, compute:  \n$$\n\\mathbb{E} = \\sum_{i=1}^n \\left(1 - \\prod_{k \\in N_i} (1 - c_{k,i}) \\right)\n$$\n\nOutput $ \\mathbb{E} \\mod 998244353 $, with all probabilities represented as modular inverses modulo $ 998244353 $.","simple_statement":"Monocarp enters n contests and wants to win T-shirts of sizes a₁, a₂, ..., aₙ for his friends.  \nWhen registering for contest i, he asks for size aᵢ.  \nBut he might get:  \n- size aᵢ-1 with probability p = P/10⁶,  \n- size aᵢ+1 with probability q = Q/10⁶,  \n- size aᵢ with probability 1-p-q.  \n\nAfter all contests, he gives one T-shirt of size aᵢ to friend i only if he got at least one T-shirt of that size.  \nFind the expected number of friends who get a T-shirt.  \nAnswer modulo 998244353.","has_page_source":false}