DFT에 관한 또 하나의 문제

$p$는 소수이고, $a=(a\_0, a\_1, \ldots, a\_{n-1})$는 정수 $n$개로 이루어진 배열이다. 여기서 $p=Kn+1$을 만족하는 양의 정수 $K$가 있다. 모든 $k=0, 1, \ldots, n-1$에 대해

$\hat{a}\_k = \left( \sum\_{j=0}^{n-1} a\_j w^{jk} \right) \bmod p$

이 성립하면 배열 $\hat{a}=(\hat{a}\_0, \hat{a}\_1, \ldots, \hat{a}\_{n-1})$를 $a$의 이산 푸리에 변환이라 하고, $\hat{a} = \mathrm{DFT}(a)$로 쓴다. 여기서 $w$는 법 $p$에서의 $n$차 원시 단위근이다. 즉 $w^n \equiv 1 \pmod p$이고, $0 < i < n$인 모든 $i$에 대해 $w^i \not\equiv 1 \pmod p$이다.

$w$는 여러 값이 가능하므로 DFT가 하나로 정해지지 않는다. 이 문제에서는 다음 방식으로 $w$를 정한다. $g$를 법 $p$의 생성원이라 하자. 즉 $0 < x < p$인 모든 $x$에 대해 $x = g^r \bmod p$인 $0 \leq r < p-1$이 존재한다. 이런 $g$ 중 가장 작은 양의 값을 고르고, $w = g^K \bmod p$로 둔다.

\mathrm{DFT}^{(m)}(a) = \underbrace{\mathrm{DFT}(\mathrm{DFT}( \ldots \mathrm{DFT}(a) \ldots ))}_{\text{m번}}로 정의한다. 이 문제의 과제는 $\mathrm{DFT}^{(m)}(a)$를 구하는 것이다.

첫 줄에 공백으로 구분된 세 정수 $n$ ($2 \leq n \leq 3 \cdot 10^5$), $p$ ($5 \leq p \leq 10^9+7$), $m$ ($0 \leq m \leq 10^{18}$)이 주어진다. $p$는 소수이고, $n$은 $p-1$을 나누어떨어뜨린다고 보장된다.

둘째 줄에는 공백으로 구분된 정수 $n$개 $a_0, a_1, \ldots, a_{n-1}$ ($0 \leq a_i < p$)이 주어진다.

연산을 적용한 뒤의 배열 $a'_0, a'_1, \ldots, a'_{n-1}$을 공백으로 구분하여 $n$개 출력한다.

예시에서 $p=61$의 가장 작은 생성원은 $g=2$이다. $K = \frac{61 - 1}{6} = 10$이므로, 법 61에서 6차 원시 단위근으로 $w = 2^{10} \bmod 61 = 48$을 고른다. 처음 몇 번의 반복 결과는 다음과 같다.

• $\mathrm{DFT}^{(0)}(a) = (24, 17, 39, 52, 25, 7)$
• $\mathrm{DFT}^{(1)}(a) = (42, 55, 25, 12, 39, 32)$
• $\mathrm{DFT}^{(2)}(a) = (22, 42, 28, 7, 51, 41)$
• $\mathrm{DFT}^{(3)}(a) = (8, 9, 51, 11, 28, 25)$
• $\mathrm{DFT}^{(4)}(a) = (10, 2, 1, 42, 46, 8)$