English · Original
Chinese · Translation
Formal · Original
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 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\].
Your 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_.
## Input
The 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.
## Output
You should output the array _A_ from left to right.
[samples]
## Note
The multiplicative order of a number _a_ modulo _Q_ , is the smallest natural number _x_ such that _a__x_ _mod_ _Q_ = 1. For example, .
考虑一个包含 #cf_span[N] 个元素的数组 #cf_span[A]，所有元素均为相同的整数 #cf_span[a]。
定义乘积变换为同时执行更新 #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]]。
你的任务是计算经过 #cf_span[M] 次乘积变换后的数组 #cf_span[A]。由于数字可能变得很大，你需要输出它们对 #cf_span[Q] 取模的结果。
输入的第一行也是唯一一行包含四个整数 #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] 的乘法阶，详见注释。
请从左到右输出数组 #cf_span[A]。
整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，是指最小的自然数 #cf_span[x]，使得 #cf_span[a^x mod Q = 1]。例如，。
## Input
输入的第一行也是唯一一行包含四个整数 #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] 的乘法阶，详见注释。
## Output
请从左到右输出数组 #cf_span[A]。
[samples]
## Note
整数 #cf_span[a] 模 #cf_span[Q] 的乘法阶，是指最小的自然数 #cf_span[x]，使得 #cf_span[a^x mod Q = 1]。例如，。
**Definitions**
Let $ N, M, a, Q \in \mathbb{Z} $ with $ Q $ prime, $ a \geq 2 $, $ N \geq 2 $.
Let $ A^{(0)} = (a, a, \dots, a) \in \mathbb{Z}^N $ be the initial array.
Let $ \omega $ be the multiplicative order of $ a $ modulo $ Q $, i.e., the smallest positive integer $ x $ such that $ a^x \equiv 1 \pmod{Q} $.
**Transformation Rule**
For $ m \geq 1 $, define the product transformation $ A^{(m)} $ from $ A^{(m-1)} $ as:
$$
A_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)}.
$$
**Constraints**
1. $ 7 \leq Q \leq 10^9 + 123 $
2. $ 2 \leq a \leq 10^6 + 123 $
3. $ Q $ is prime
4. $ \omega $ is the multiplicative order of $ a \mod Q $
**Objective**
Compute $ 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) $.
API Response (JSON)
{
"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...",
"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[...",
"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 mu...",
"is_translate": false,
"language": "Formal"
}
]
}