Sto avendo dei problemi a risolvere “Camera dei segreti”, ho bisogno di utilizzare la trasformata di Fourier per le moltiplicazioni tra polinomi. Va tutto bene finchè non devo aggiungere il modulo. Sto consultando https://cp-algorithms.com/algebra/fft.html#number-theoretic-transform e vedo che il sito propone questo metodo.
Io ho:
#define mod 104857601
const int root = 3;
const int root_1 = 34952534;
const int root_pw = 1 << 20;
Ovviamente il modulo è quello proposto dal problema di Camera dei segreti.
Non so se ho calcolato bene la radice e la radice inversa.
Per la costante “root_pw” non ho capito che calcolo bisogna fare.
Ciao, in realtà il problema passa agevolmente anche con FFT (io ho usato quello di USACO guide).
Per NTT root_pw in realtà può essere un qualunque numero 2^k tale che esista una radice (primitiva) 2^k-esima dell’unità sotto il tuo modulo. 2^k è la dimensione della più grande trasformata che puoi fare, quindi va scelto sufficientemente grande (però 2^{20} dovrebbe bastare per questo problema)
root deve essere una radice root_pw-esima primitiva di 1 (e mi pare che in realtà root ** root_pw % mod != 1 al momento).
root_1 deve essere l’inverso di root modulo mod, cioè quel numero tale che root * root_1 % mod == 1. Puoi calcolarlo con Euclide esteso oppure facendo root ** (mod - 2)
