Soit $p$ un nombre premier et $a = (a_0, a_1, \dots, a_{n-1})$ un tableau de $n$ entiers, où $p = Kn + 1$ pour un certain entier positif $K$. Nous disons que le tableau $\hat{a} = (\hat{a}_0, \hat{a}_1, \dots, \hat{a}_{n-1})$ est la transformée de Fourier discrète (DFT) du tableau $a$ si, pour tout $k = 0, 1, \dots, n-1$, la condition suivante est vérifiée :
$$\hat{a}_k = \left( \sum_{j=0}^{n-1} a_j w^{jk} \right) \pmod p$$
et nous écrivons simplement $\hat{a} = \text{DFT}(a)$. Ici, $w$ désigne une racine primitive $n$-ième de l'unité modulo $p$, c'est-à-dire que nous avons $w^n \equiv 1 \pmod p$ et, pour tout $i$ tel que $0 < i < n$, $w^i \not\equiv 1 \pmod p$.
Notez qu'il peut y avoir plusieurs choix pour $w$, donc la DFT ne sera pas unique. Clarifions comment la trouver de manière unique pour ce problème. Soit $g$ un générateur modulo $p$, c'est-à-dire que pour tout $x$ tel que $0 < x < p$, il existe un entier positif $r$ tel que $0 \le r < p-1$ et $x = g^r \pmod p$. Vous pouvez trouver la plus petite valeur positive pour $g$ qui fonctionne et choisir $w = g^K \pmod p$.
Maintenant, nous définissons $\text{DFT}^{(m)}(a) = \underbrace{\text{DFT}(\text{DFT}(\dots \text{DFT}(a)\dots))}_{m \text{ fois}}$, donc votre tâche est simplement de trouver $\text{DFT}^{(m)}(a)$.
Entrée
La première ligne contient trois entiers séparés par des espaces : $n$ ($2 \le n \le 3 \cdot 10^5$), $p$ ($5 \le p \le 10^9+7$) et $m$ ($0 \le m \le 10^{18}$), les paramètres du problème décrit ci-dessus. Il est garanti que $p$ est premier et que $n$ divise $p-1$ exactement.
La deuxième ligne contient $n$ entiers séparés par des espaces $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$), le tableau $a$.
Sortie
Affichez $n$ entiers séparés par des espaces $a'_0, a'_1, \dots, a'_{n-1}$, le tableau résultant après avoir effectué l'opération indiquée dans le problème.
Exemples
Entrée 1
6 61 4 24 17 39 52 25 7
Sortie 1
10 2 1 42 46 8
Remarque
Dans l'exemple de test, le plus petit générateur possible pour $p = 61$ est $g = 2$. Nous avons $K = \frac{61-1}{6} = 10$, donc nous choisissons $w = 2^{10} \pmod{61} = 48$ pour être la racine primitive 6-ième de l'unité modulo 61. Les premières itérations de la DFT sont les suivantes :
- $\text{DFT}^{(0)}(a) = (24, 17, 39, 52, 25, 7)$
- $\text{DFT}^{(1)}(a) = (42, 55, 25, 12, 39, 32)$
- $\text{DFT}^{(2)}(a) = (22, 42, 28, 7, 51, 41)$
- $\text{DFT}^{(3)}(a) = (8, 9, 51, 11, 28, 25)$
- $\text{DFT}^{(4)}(a) = (10, 2, 1, 42, 46, 8)$