{"problem":{"name":"A. Random Mood","description":{"content":"_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._ Limak is always either happy or sad. His mood switches with probability $p$ every se","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264A"},"statements":[{"statement_type":"Markdown","content":"_This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here._\n\nLimak is always either happy or sad. His mood switches with probability $p$ every second. If Limak is happy right now, what is the probability that he's happy after $n$ seconds?\n\nAn integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point.\n\nPrint one line with the answer. The absolute error allowed is $10^(-6)$.\n\nIn the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy.\n\nIn the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all.\n\n## Input\n\nAn integer $n$ ($1 <= n <= 10^9$) and a real value $p$ ($0 < p < 1$) with at most 9 digits after floating point.\n\n## Output\n\nPrint one line with the answer. The absolute error allowed is $10^(-6)$.\n\n[samples]\n\n## Note\n\nIn the first sample test, there's probability $0. 7$ that Limak changes his mood from happy to sad. Otherwise (with probability $0. 3$), he stays happy.In the second sample test, the answer is $0. 1 dot.op 0. 1 + 0. 9 dot.op 0. 9 = 0. 82$ because we want Limak either to switch his mood twice or not to change the mood at all.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p \\in (0,1) $ be the probability of mood switch per second.  \nLet $ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $, be the number of seconds.  \nLet $ h_n $ be the probability that Limak is happy after $ n $ seconds, given he starts happy.\n\n**Constraints**  \n$ 0 < p < 1 $, with at most 9 decimal digits.  \n$ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $\n\n**Objective**  \nCompute $ h_n $, where the state transition is governed by:  \n$$\nh_0 = 1, \\quad h_{k} = (1 - p) h_{k-1} + p (1 - h_{k-1}) \\quad \\text{for } k \\geq 1\n$$  \nEquivalently:  \n$$\nh_n = \\frac{1 + (1 - 2p)^n}{2}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}