{"problem":{"name":"F. Product transformation","description":{"content":"Consider an array _A_ with _N_ elements, all being the same integer _a_. Define the product transformation as a simultaneous update _A__i_ = _A__i_·_A__i_ + 1, that is multiplying each element to the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF852F"},"statements":[{"statement_type":"Markdown","content":"Consider an array _A_ with _N_ elements, all being the same integer _a_.\n\nDefine the product transformation as a simultaneous update _A__i_ = _A__i_·_A__i_ + 1, that is multiplying each element to the element right to it for , with the last number _A__N_ remaining the same. For example, if we start with an array _A_ with _a_ = 2 and _N_ = 4, then after one product transformation _A_ = \\[4,  4,  4,  2\\], and after two product transformations _A_ = \\[16,  16,  8,  2\\].\n\nYour simple task is to calculate the array _A_ after _M_ product transformations. Since the numbers can get quite big you should output them modulo _Q_.\n\n## Input\n\nThe first and only line of input contains four integers _N_, _M_, _a_, _Q_ (7 ≤ _Q_ ≤ 109 + 123, 2 ≤ _a_ ≤ 106 + 123, , is prime), where is the multiplicative order of the integer _a_ modulo _Q_, see notes for definition.\n\n## Output\n\nYou should output the array _A_ from left to right.\n\n[samples]\n\n## Note\n\nThe multiplicative order of a number _a_ modulo _Q_ , is the smallest natural number _x_ such that _a__x_ _mod_ _Q_ = 1. For example, .","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"考虑一个包含 #cf_span[N] 个元素的数组 #cf_span[A]，所有元素均为相同的整数 #cf_span[a]。\n\n定义乘积变换为同时执行更新 #cf_span[Ai = Ai·Ai + 1]，即对每个元素将其与右侧元素相乘（最后一个元素 #cf_span[AN] 保持不变）。例如，若我们从数组 #cf_span[A] 开始，其中 #cf_span[a = 2] 且 #cf_span[N = 4]，则经过一次乘积变换后 #cf_span[A = [4, 4, 4, 2]]，经过两次乘积变换后 #cf_span[A = [16, 16, 8, 2]]。\n\n你的任务是计算经过 #cf_span[M] 次乘积变换后的数组 #cf_span[A]。由于数字可能变得很大，你需要输出它们对 #cf_span[Q] 取模的结果。\n\n输入的第一行也是唯一一行包含四个整数 #cf_span[N], #cf_span[M], #cf_span[a], #cf_span[Q]（#cf_span[7 ≤ Q ≤ 10^9 + 123], #cf_span[2 ≤ a ≤ 10^6 + 123],  是质数），其中  是整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，详见注释。\n\n请从左到右输出数组 #cf_span[A]。\n\n整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，是指最小的自然数 #cf_span[x]，使得 #cf_span[a^x mod Q = 1]。例如，。\n\n## Input\n\n输入的第一行也是唯一一行包含四个整数 #cf_span[N], #cf_span[M], #cf_span[a], #cf_span[Q]（#cf_span[7 ≤ Q ≤ 10^9 + 123], #cf_span[2 ≤ a ≤ 10^6 + 123],  是质数），其中  是整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，详见注释。\n\n## Output\n\n请从左到右输出数组 #cf_span[A]。\n\n[samples]\n\n## Note\n\n整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，是指最小的自然数 #cf_span[x]，使得 #cf_span[a^x mod Q = 1]。例如，。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M, a, Q \\in \\mathbb{Z} $ with $ Q $ prime, $ a \\geq 2 $, $ N \\geq 2 $.  \nLet $ A^{(0)} = (a, a, \\dots, a) \\in \\mathbb{Z}^N $ be the initial array.  \nLet $ \\omega $ be the multiplicative order of $ a $ modulo $ Q $, i.e., the smallest positive integer $ x $ such that $ a^x \\equiv 1 \\pmod{Q} $.\n\n**Transformation Rule**  \nFor $ m \\geq 1 $, define the product transformation $ A^{(m)} $ from $ A^{(m-1)} $ as:  \n$$\nA_i^{(m)} = A_i^{(m-1)} \\cdot A_{i+1}^{(m-1)} \\quad \\text{for } i = 1, 2, \\dots, N-1, \\quad A_N^{(m)} = A_N^{(m-1)}.\n$$\n\n**Constraints**  \n1. $ 7 \\leq Q \\leq 10^9 + 123 $  \n2. $ 2 \\leq a \\leq 10^6 + 123 $  \n3. $ Q $ is prime  \n4. $ \\omega $ is the multiplicative order of $ a \\mod Q $\n\n**Objective**  \nCompute $ A^{(M)} \\mod Q $, i.e., output the array $ (A_1^{(M)} \\mod Q, A_2^{(M)} \\mod Q, \\dots, A_N^{(M)} \\mod Q) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF852F","tags":["combinatorics","math","number theory"],"sample_group":[["2 2 2 7","1 2"]],"created_at":"2026-03-03 11:00:39"}}