Antes de las competencias provinciales, creí que se examinaría temas como transformadas rápidas o álgebra polinomial, así que me preparé intensivamente. Finalmente, ninguno de esos temas apareció en el examen.

¿Qué pasó con nuestros problemas excelentes de complejidad no polinomial? [Señalando cartel]

Así que aquí está un resumen de lo que aprendí durante mi preparación.

Tenemos una plantilla de NTT que deberíamos memorizar completamente:

const int mod=998244353,iG=(mod+1)/3;
int bit_rev[1<<22];
void NTT(int *poli, int tamano, int sentido){
	for(int i=0;i<tamano;i++)if(i<bit_rev[i])swap(poli[i],poli[bit_rev[i]]);
	for(int mid=1;mid<tamano;mid<<=1){
		int w=potencia(sentido?iG:3,(mod-1)/(mid<<1));
		for(int i=0;i<tamano;i+=(mid<<1)){
			int p=1;
			for(int j=0;j<mid;j++,p=p*w%mod){
				int u=poli[i+j],v=poli[i+mid+j]*p%mod;
				poli[i+j]=(u+v)%mod;
				poli[i+mid+j]=(u+mod-v)%mod;
			}
		}
	}
	if(sentido){
		int I=potencia(tamano,mod-2);
		for(int i=0;i<tamano;i++)poli[i]=poli[i]*I%mod;
	}
}

Pregunta: ¿Qué hace este código?

Si hemos estudiado la FFT (Transformada Rápida de Fourier), la respuesta es sencilla. La FFT convierte rápidamente un polinomio en sus valores de evaluación, mientras que NTT realiza esta transformación en un campo modular primo. Es decir, dado un polinomio \(A\), NTT convierte \(A\) en los valores de evaluación en varios puntos. Al calcular el producto de polinomios, solo necesitamos multiplicar los valores de evaluación correspondientes. Esta es su aplicación más básica:

void Multiplicar(int *pol1, int n, int *pol2, int m){
	int tamano=1,l=0;
	while(tamano<=n+m)tamano<<=1,l++;
	for(int i=0;i<tamano;i++)bit_rev[i]=(bit_rev[i>>1]>>1)|((i&1)<<(l-1));
	NTT(pol1,tamano,0);NTT(pol2,tamano,0);
	for(int i=0;i<=tamano;i++)pol1[i]=pol1[i]*pol2[i]%mod;
	NTT(pol1,tamano,1);
}

Esto cambia la multiplicación de polinomios, que originalmente era de complejidad cuadrática, a una complejidad logarítmica.

Sin embargo, los problemas algebraicos generalmente no solo involucran multiplicación, sino también división. La división es equivalente al inverso multiplicativo. Es decir, para un polinomio \(A\), buscamos un polinomio \(B\) tal que \(AB\equiv 1 \pmod {x^{n}}\). Podemos afirmar que existe una solución gracias al algoritmo de división polinomial estándar.

Pero calcular esto directamente sigue siendo lento, por lo que consideramos un enfoque iterativo. Supongamos que ya hemos calculado \(B_k\) tal que \(AB_k\equiv 1\pmod {x^{2^k}}\), y queremos encontrar \(B_{k+1}\).

Tenemos \(AB_k\equiv 1 \pmod {x^{2^k}}\Leftrightarrow AB_k-1\equiv 0\pmod {x^{2^k}}\). Sea \(B_{k+1}=B_k+x^{2^k}C\), con \(grado(C)<m\).

Entonces \(A(B_k+x^{2^k}C)\equiv 1\pmod {x^{2^{k+1}}}\Leftrightarrow AB_k+x^{2^k}AC\equiv 1\pmod {x^{2^{k+1}}}\).

Sea \(AB_k=1+x^{2^k}D\), tenemos \(1+x^{2^k}D+x^{2^k}AC\equiv 1\pmod {x^{2^{k+1}}}\Leftrightarow x^{2^k}AC\equiv -x^{2^k}D\pmod{x^{2^{k+1}}}\Leftrightarrow AC\equiv -D\pmod{x^{2^k}}\).

De la definición de \(B_k\), tenemos \(C\equiv -B_k D\pmod {x^{2^k}}\). Además, como \(AB_k=1+x^{2^k}D\), entonces \(D=\frac{AB_k-1}{x^{2^k}}\), por lo tanto \(C \equiv -B_k \cdot \frac{A B_k - 1}{x^{2^k}} \pmod{x^{2^k}}\), y \(x^{2^k}C\equiv -B_k(AB_k-1)\pmod{x^{2^{k+1}}}\).

Así \(B_{k+1}=B_k+x^{2^k}C\equiv B_k-B_k(AB_k-1)=2B_k-AB_k^2=B_k(2-AB_k)\pmod{x^{2^{k+1}}}\), y podemos usar NTT para el cálculo:

void Inverso(int *pol, int *inv, int grado){
	if(!grado) {
		inv[0]=potencia(pol[0],mod-2);
		return;
	}
	Inverso(pol,inv,grado/2);
	int tamano=1;
	while(tamano<=grado*2)tamano<<=1;
	for(int i=0;i<=grado;i++)temp[i]=pol[i];
	for(int i=grado+1;i<=tamano;i++)temp[i]=0;
	NTT(inv,tamano,0);NTT(temp,tamano,0);
	for(int i=0;i<=tamano;i++)inv[i]=(inv[i]*2%mod-inv[i]*inv[i]%mod*temp[i]%mod+mod)%mod;
	NTT(inv,tamano,1);
	for(int i=grado+1;i<=tamano;i++)inv[i]=0;
}