{"problem":{"name":"J. Jar of Water Game","description":{"content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10234J"},"statements":[{"statement_type":"Markdown","content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10234J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}