---
tags: fft, ntt, fwt, dft, polynomials, algebra, number-theory, combinatorics, convolution, interpolation, primitive-roots, generators
---

# FFT parte 2

## Precisión
Al usar la FFT con números complejos con entradas ``double`` hay cierta pérdida de precisión y puede aparecer un error.

Supongamos que multiplicamos dos polinomios $A(x)$ y $B(x)$, ambos de grado $n$ cuyos coeficientes no exceden $M$. El peor caso se da al obtener un coeficiente igual a $(n+1)M^2$.

Ejemplo: si $n=4$ y $M=100$, el coeficiente más alto que se podrá obtener es $50000$.

En un ``double`` a lo más podemos guardar números aproximadamente del orden $10^{13}$, mientras que en un ``long double`` hasta $10^{16}$.

Código auxiliar para multiplicar dos polinomios de enteros, asumiendo que la precisión es suficiente:

vector<int> operator*(const vector<int>& A, const vector<int>& B){
  int m = A.size(), n = B.size();
  int sz = m+n-1;
  poly a(m), b(n);
  for(int i = 0; i < m; ++i){
    a[i] = A[i];
  }
  for(int i = 0; i < n; ++i){
    b[i] = B[i];
  }
  poly c = a*b;
  vector<int> C(sz);
  for(int i = 0; i < sz; ++i){
    C[i] = round(c[i].real());
  }
  return C;
}

## Problemas
**[Golf bot](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4744)**
Dado un arreglo $A$ de enteros no negativos y un arreglo $B$ de objetivos, determinar cuántos elementos de $B$ se pueden expresar como suma de uno o dos elementos de $A$.

Sea $P(x)$ un polinomio tal que $P[k]=1$ si $k \in A$, y $P[k]=0$ si $k \not \in A$. Entonces $P(x)*P(x)$ va a representar todas las posibles sumas a las que puedo llegar usando elementos de $A$, o sea, el coeficiente de $x^k$ de $[P(x)]^2$ nos dirá de cuántas formas pude sumar $k$ usando dos elementos de $A$.

La complejidad es $O(MAX \log MAX)$, donde $MAX$ es el valor máximo de $A$.

**[Maximum self matching](https://www.spoj.com/problems/MAXMATCH/)**
Resolvamos el problema para cada letra por separado ('a', 'b' y 'c') y al final sumamos los tres resultados:
- Sea $P_a(x)$ el polinomio que representa a la cadena únicamente con letras 'a', es decir, el coeficiente de $x^k$ es $1$ si $s[k]=a$ y es $0$ si $s[k] \neq a$.
- Para hallar las posiciones donde hay matching, vemos que si corremos la cadena $i$ lugares, entonces $\displaystyle m_s(i)=\sum_{j = 0}^{\infty} P_a[j+i] * P_a[j]$. Esta operación también se conoce como correlación, veamos cómo transformarla a una convolución y así aplicar la FFT.
- Sea $P_a'(x)$ el polinomio obtenido al poner de reversa los coeficientes de $P_a(x)$, es decir, $P_a[k] = P_a'[n-1-k]$.
- Reemplazando tenemos que: $\displaystyle m_s(i)=\sum_{j = 0}^{\infty} P_a[j+i] * P_a'[n-1-j]$. Vemos que la suma de los índices es ahora $(j+i)+(n-1-j)=i+n-1$.
- Podemos interpretar eso de la siguiente manera: si multiplicamos los polinomios $P_a(x)$ y $P_a'(x)$, entonces el valor de $m_s(i)$ lo encontraremos en el coeficiente de $x^{i+n-1}$.
- Finalmente, definimos a $P_b(x)$ y a $P_c(x)$ de forma similar, hacemos lo mismo y combinamos ya para obtener todos los valores completos de $m_s(i)$.

**[K-inversions](https://open.kattis.com/problems/kinversions)**
- Sea $P_a(x)$ el polinomio que representa a la cadena únicamente con letras 'A', es decir, $P_a[k]=1$ si $s[k]=A$ y $P_a[k]=0$ en caso contrario.
- Sea $P_b(x)$ el polinimio que representa a la cadena únicamente con letras 'B' y con potencias negativas, es decir, $P_b[-k]=1$ si $s[k]=B$ y $P_b[-k]=0$ en caso contrario.
- Al multiplicar $P_a(x) * P_b(x)$, obtendremos un nuevo polinomio cuyo coeficiente de $x^k$ nos indica el número de $k-$inversiones.
- Para programarlo, tenemos potencias negativas en $P_b(x)$ y eso no se puede implementar directamente. Sea $P_b'(x)=x^{n-1}P_b(x)$, es decir, $P_b[-k] = P_b'[n-1-k]$. Es fácil ver que $P_b'(x)$ ya no tiene potencias negativas.
- Entonces el producto es ahora $P_a(x) * P_b'(x) = P_a(x) * x^{n-1} P_b(x)$. Es decir, ahora la respuesta está recorrida $n-1$ posiciones. Por lo tanto, el número de $k-$inversiones ahora lo vamos a encontrar en el coeficiente de $x^{k+n-1}$ de dicho producto.

**[Thief in a shop](https://codeforces.com/problemset/problem/632/E)**
- Para hallar todos los costos posibles de escoger exactamente $k$ productos, definimos el polinomio $\displaystyle P(x)=\sum_{i=1}^{n} x^{a_i}$.
- Entonces, la respuesta para un costo específico (el número de maneras de obtenerlo), digamos $c$, la encontraremos en el coeficiente de $x^c$ en el polinomio $[P(x)]^k$. Entonces, simplemente hay que imprimir las potencias que tengan un coeficiente mayor a cero, pues esos costos sí fueron posibles.
- Complejidad: $O(m \log m \log k)$, donde $\displaystyle m=\left( \max_{1 \leq i \leq n}a_i \right)*k$, pues hacemos exponenciación binaria sobre el polinomio. Pero se puede reducir a $O(m \log m + m \log k)$ si hacemos exponenciación binaria sobre cada término de la DFT del polinomio $P(x)$.
- Los coeficientes de $[P(x)]^k$ pueden crecer muchísimo, entonces como el problema solo pide ver las sumas que aparecen con $k$ términos pero no su conteo, en cada multiplicación que hagamos vamos a truncar en $1$ los coeficientes que sean mayores o iguales a $1$, y los que son $0$ se quedan en $0$.

**[Very Fast Multiplication](https://www.spoj.com/problems/VFMUL/)**
Dados dos números $a$ y $b$ en decimal, hallar su producto.

- Vamos a interpretar a $a$ y a $b$ como dos polinomios $A(x)$ y $B(x)$ evaluados en $10$, cuyos coeficientes son los dígitos. Es decir, $a=A(10)$ y $b=B(10)$.
- Sabemos que $c=ab=A(10)B(10)$. Sea $C(x)$ la representación de $c$ en forma de polinomio, entonces $c=C(10)$. Sabemos que $C(x)=A(x)B(x)$, la cual se puede hacer de forma eficiente con FFT.
- El último paso es recuperar $c$ a partir de los coeficientes de $C(x)$. Se tiene que cumplir que los coeficientes sean menores a 10, y para forzarlo hay que realizar los *carries* del menos significativo al más significativo.



**[Tile Cutting](https://open.kattis.com/problems/tiles)**
- Un área específica $A$ se puede escribir como $A=ac+bd$, donde $a,b,c,d \in \mathbb{N}$. Sea $m=ac$ y $n=bd$, entonces $A=m+n$.
- Ejemplo: si $A=5$, entonces $A = 1+4 = 2+3 = 3+2 = 4+1$.
- Ejemplo: si $m=15$, entonces $15 = 1 \times 15 = 3 \times 5 = 5 \times 3 = 15 \times 1$.
- Dada una $m$, sabemos que el número de formas de expresarla como un producto de dos enteros positivos es igual al número de divisores de $m$. Lo mismo pasa con $n$.
- Entonces, sea $P(x)$ tal que $P[i] = \sigma_0(i)$, donde $\sigma_0(n)$ es el número de divisores de $n$. Este arreglo se puede precalcular con criba de divisores.
- Entonces, el polinomio $P(x)^2$ nos indicará de cuántas formas puedo obtener un valor específico de $A$, y dicho número de formas estará en el coeficiente de $x^A$.
- Finalmente, para responder las queries del número máximo de formas en un intervalo de áreas, podemos usar un Segment Tree o una Sparse Table, recordando guardar también los índices junto con sus coeficientes.

**[Emma and sum of products](https://www.hackerrank.com/challenges/emma-and-sum-of-products/problem)**

Tenemos un arreglo $A$ con $n$ enteros positivos. Sea $s_k$ ($1 \leq k \leq n$) la suma de los productos de todos los posibles subarreglos de $A$ con $k$ elementos. Hallar todos los valores de $s_k$ módulo $10^5+3$.

Por ejemplo, si $A=[1,2,3,4]$, tenemos que:
- Para $k=1$ hay $\binom{4}{1}=4$ formas de escoger subarreglos de tamaño 1: $[1]$, $[2]$, $[3]$, $[4]$. Por lo tanto, $s_1=1+2+3+4=10$.
- Para $k=2$ hay $\binom{4}{2}=6$ formas de escoger subarreglos de tamaño 2: $[1,2]$, $[1,3]$, $[1,4]$, $[2,3]$, $[2,4]$, $[3,4]$. Por lo tanto, $s_2=(1 \times 2) + (1 \times 3) + (1 \times 4) + (2 \times 3) + (2 \times 4) + (3 \times 4) = 35$.
- Para $k=3$ hay $\binom{4}{3}=4$ formas de escoger subarreglos de tamaño 3: $[1,2,3]$, $[1,2,4]$, $[1,3,4]$, $[2,3,4]$. Por lo tanto, $s_3 = (1 \times 2 \times 3) + (1 \times 2 \times 4) + (1 \times 3 \times 4) + (2 \times 3 \times 4) = 50$.
- Para $k=4$ hay $\binom{4}{4}=1$ forma de escoger subarreglos de tamaño 4: $[1,2,3,4]$. Por lo tanto, $s_4 = 1 \times 2 \times 3 \times 4 = 24$.

Consideremos el polinomio $P(x)=(1+x)(1+2x)(1+3x)(1+4x)$. Vemos que tiene grado 4, ahora determinemos sus coeficientes:
- Para hallar el coeficiente de $x$ fijamos el término lineal de $1$ monomio. Vemos que ese término solo puede multiplicarse por los términos constantes (que son todos 1's) de los otros monomios para obtener solo una $x$. Hay $\binom{4}{1}=4$ formas de fijar este término.
- Para hallar el coeficiente de $x^2$ fijamos los términos lineales de $2$ monomios, por lo que los demás términos tendrán que ser puros 1's. Hay $\binom{4}{2}=6$ formas de fijar estos dos términos.
- Para hallar el coeficiente de $x^3$ fijamos los términos lineales de $3$ monomios, el resto serán 1's. Hay $\binom{4}{3}=4$ formas de hacerlo.
- Para hallar el coeficiente de $x^4$ solo podemos fijar los $4$ términos lineales de cada monimio. Claramente esto solo se puede hacer de $\binom{4}{4}=1$ forma.

Con lo anterior concluímos que $P(x) = 1 + s_1x + s_2x^2 + s_3x^3 + s_4x^4$.

De forma general, $P(x)=(1+a_1x)(1+a_2x) \cdots (1+a_nx) = 1 + s_1x + s_2x^2 + \cdots + s_nx^n$, por lo que hemos reducido el problema a expandir y hallar los coeficientes de $P(x)$.

Una forma es ir multiplicando en secuencia cada monomio usando FFT, pero eso tendría una complejidad de $O(1 \log 1) + O(2 \log 2) + \cdots + O(n \log n) = O(n^2 \log n)$, la cual no es aceptable.

En la idea anterior estamos multiplicando polinomios de grados muy disparejos, pues los monomios siempre tienen grado 1. Otra forma es usar divide y vencerás para intentar balancear estos productos: sea $Q(l,r)=(1+a_lx)(1+a_{l+1}x) \cdots (1+a_rx)$. La respuesta será $Q(1,n)$, y tenemos la recurrencia:
$$
Q(l,r) = \begin{cases}
1 + a_lx &\mbox{si $l=r$} \\
Q(l,m) * Q(m+1,r) &\mbox{donde $m=\lfloor (l+r)/2 \rfloor$}
\end{cases}
$$

La complejidad $T(n)$ cumple que $T(n)=2T(n/2) + O(n \log n)$, que es igual a $T(n)=O(n \log^2 n)$, la cual ya es aceptable.


Debido a que los coeficientes de estas multiplicaciones son menores a $10^5+3$ y $n \leq 3 \times 10^4$, el máximo coeficiente intermedio antes de modular es del orden $(10^5+2)^2(3 \times 10^4+1) \approx 3 \times 10^{14}$, por lo que tendremos que usar ``long double`` si decidimos usar FFT con números complejos.

### Duel
Dada una cadena $s$ de tamaño $n$ de ceros y unos, donde los ceros son arbustos y los unos son árboles, determinar cuántas ternas $(i,j,k)$ existen tal que $s[i]$, $s[j]$ y $s[k]$ son árboles, $i<j<k$ y $s[j]$ está enmedio de $s[i]$ y $s[k]$.

Una forma de hacerlo es fijar el centro tal que sea un árbol, o sea, la posiciones $j$ tal que $s[j]=1$, y buscar a la izquierda y a la derecha unos con la misma distancia.

Requerimos que $j$ sea el punto medio de $i$ y $k$, esto es equivalente a $(i+k)/2=j$, o sea, $i+k=2j$. El primer paso es hallar todas las posibles sumas de $i+k$, donde $s[i]$ y $s[k]$ son unos. Sea $P(x)$ tal que $P[i]=1$ si y solo si $s_i=1$. Entonces $[P(x)]^2$ va a decirme todas las posibles sumas $i+k$ y de cuántas formas las obtuve.

Para forzar $i<k$ primero vamos a quitar las sumas cuando $i=k$: estas las obtengo a través de $P(x^2)$. Por lo tanto, hasta ahora llevamos $P(x)^2 - P(x^2)$.

Para quitar las sumas reflejadas, solo dividimos entre 2: $Q(x)=\frac{P(x)^2 - P(x^2)}{2}$.

Por último, fijemos el centro $j$ tal que $s[j]=1$ y a la respuesta le sumo $Q[2j]$.

Ejemplo:

### Equation
Hallar el número de soluciones $(x,y,z)$ tales que $x^n + y^n \equiv z^n \mod{m}$, $1 \leq x \leq y < m$, $1 \leq z < m$.

Sea $\displaystyle P(x)=\sum_{i=1}^{m-1} x^{i^n \mod m}$, entonces $P(x)^2$ nos dirá todas las posibles sumas de la forma $x^n+y^n \mod m$. Pero como hay que seguir modulando las sumas, realmente la convolución a realizar es circular.

Para considerar la condición de que $x \leq y$, primero hacemos que $x < y$, y por el problema anterior, eso está representado en $\frac{1}{2}({P(x)^2 - P(x^2)})$. Luego consideremos el caso $x=y$, por lo tanto, $Q(x)=\frac{1}{2}({P(x)^2 - P(x^2)})+P(x^2) = \frac{1}{2}({P(x)^2 + P(x^2)})$.

Finalmente, fijamos $z$ desde $1$ hasta $m-1$ y sumamos a la respuesta $Q[z^n \mod m]$.

Ejemplo:

---
---

## Generalización a $\mathbb{F}_p$ (NTT, Number Theoretic Transform)
- Conceptos previos: sea $p$ un número primo. Entonces definimos al conjunto $\mathbb{F}_p$ como el conjunto $\{0, 1, \ldots, p-1\}$. También se le conoce como campo finito de orden $p$.
- Ahora, definimos a $g$ como un generador módulo $p$ si se cumple que para toda $x$ tal que $1 \leq x < p$ existe una $r$ tal que $g^r \equiv x \mod p$.
- Ejemplo: si $p=7$, entonces $g=3$, ya que: $g^0=1$, $g^1=3$, $g^2=2$, $g^3=6$, $g^4=4$, $g^5=5$, $g^6=1$, $\ldots$. Entonces $g=3$ es un generador módulo 7.
- Ejemplo: si $p=7$ y $g=2$, entonces $g^0=1$, $g^1=2$, $g^2=4$, $g^3=1$, $\ldots$. Entonces $g=2$ NO es un generador módulo 7.
- De hecho, siempre existen $\varphi(p-1)$ generadores módulo $p$.
- Definimos a $r=\text{ord}_p(x)$ como el *órden multipicativo de $x$ módulo $p$*, y es la mínima $r$ positiva que cumple que $x^r \equiv 1 \mod p$.
- Ejemplo: si $p=7$ y $x=2$, tenemos que $\text{ord}_7(2)=3$ pues $2^3 \equiv 1 \mod 7$ y $2^r \not \equiv 1 \mod 7$ para $r < 3$.
- De hecho, si $g$ es un generador módulo $p$, entonces $\text{ord}_p(g)=p-1$.
- Ahora definamos a $\omega$ como una raíz $k$-ésima de la unidad si $\omega^k \equiv 1 \mod p$. Además, decimos que es primitiva si $\omega^r \not \equiv 1 \mod p$ para $1 \leq r < k$.
- Ejemplos: si $p=7$, $\omega=2$ y $k=3$, entonces 2 es una raíz cúbica de la unidad, pues $2^3 \equiv 1 \mod 7$. Además es primitiva, pues $2^1 , 2^2 \not \equiv 1 \mod 7$.
- Entonces, se puede ver que si $\omega$ es una raíz $k$-ésima primitiva de la unidad módulo $p$, entonces $\text{ord}_p(\omega) = k$.
- Supongamos que queremos hallar una raíz $N$-ésima de la unidad módulo $p$, es decir, $\omega$, para poder obtener la FFT de un vector de tamaño $N$, donde $N=2^h$. Primero supongamos que $p=b \cdot 2^h + 1$, donde $b \in \mathbb{N}$ se escoge de tal forma que $p$ sea primo.
- Sea $g$ un generador para dicho primo.
- Entonces, $\omega \equiv g^{(p-1)/N} \mod p$. Eso se cumple, pues:
- $\omega^N \equiv g^{p-1} \equiv 1 \mod p$
- Veamos ahora que $\text{ord}_p(\omega)=N$. Sea $r$ tal que $1 \leq r < N$. Entonces $\omega^r \equiv (g^{(p-1)/N})^r \equiv (g^b)^r \equiv g^{br} \mod p$. Sabemos que $bN = p-1 = \text{ord}_p(g)$, pero como $r < N$, entonces $br < bN = \text{ord}_p(g)$, entonces $g^{br} \not \equiv 1 \mod p$, es decir, $\omega^r \not \equiv 1 \mod p$, por lo tanto $\omega$ es primitiva. $\square$
- El problema que resta es hallar un generador módulo $p$. La buena noticia es que siempre el primer generador es relativamente pequeño, entonces podemos usar fuerza bruta.
- Ahora, dado un candidato a generador $g$, ¿cómo sabemos si es generador?
- Supongamos que $d>1$ es un divisor de $p-1$, entonces si $g$ es generador, $g^{(p-1)/d} \not \equiv 1 \mod p$ para toda $d$.
- Podemos mejorar esto si en lugar de tomar un divisor $d$ de $p-1$, solamente tomamos un factor primo $p_i$ de $p-1$.
- Algunos ejemplos comunes son:
- $p = 119 \cdot 2^{23} + 1 = 998244353$, $g=3$
- $p = 7 \cdot 2^{20} + 1 = 7340033$, $g=3$
- $p = 479 \cdot 2^{21} + 1 = 1004535809$, $g=3$
- Por ejemplo, tomando el primer primo $p=998244353$, vemos que $N=2^{23}$. ¿Cómo podríamos reusarlo para otros tamaños de vector menores a $2^{23}$, digamos, de tamaño $M=2^m < 2^{23}$? Lo que queremos hacer es hallar una raíz primitiva $M$-ésima de la unidad módulo $p$, digamos que es $\omega$. Entonces resulta que $\omega = g^{(p-1)/M}$.

## Módulo arbitrario
- Si tenemos dos polinomios $P(x)$ y $Q(x)$ de grado $n$ y sus coeficientes son menores a $M$, entonces el valor máximo de un coeficiente en el producto $P(x)Q(x)$ es $(n+1)(M-1)^2 \approx nM^2$. Ejemplo, si tenemos dos polinomios de grado $10^5$ y sus coeficientes van hasta $10^6$, entonces el valor máximo de un coeficiente en el producto sería $\approx 10^{17}$.
- Ahora, supongamos que queremos hallar el producto $P(x)Q(x)$ y dar los coeficientes en algún módulo de alrededor de $10^9$, digamos, $M=10^9+7$. Hay dos formas:
- La primera es usando la FFT normal. La desventaja es que al usar un tipo de dato ``long double``, la precisión se comienza a perder significativamente al llegar a $10^{16}$. Si la usamos directamente, el producto intermedio máximo podría ser hasta $\approx 10^{23}$. Una forma de resolver esto es separar el polinomio $P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$ de la siguiente forma, donde $s=\lfloor \sqrt{M} \rfloor$:
$P_0(x) = (a_0 \% s) + (a_1 \% s)x + (a_2 \% s)x^2 + \cdots + (a_n \%s) x^n$ y $P_1(x) = \lfloor \frac{a_0}{s} \rfloor +\lfloor \frac{a_1}{s} \rfloor x + \lfloor \frac{a_2}{s} \rfloor x^2 + \cdots + \lfloor \frac{a_n}{s} \rfloor x^n$. Vemos que $P(x) = s \cdot P_1(x) + P_0(x)$. Hacemos lo mismo con $Q(x)$ de tal forma que $Q(x) = s \cdot Q_1(x) + Q_0(x)$. Entonces, el producto $P(x) * Q(x)$ queda como $P(x) * Q(x) =s^2 P_1(x) * Q_1(x) + s(P_1(x) * Q_0(x) + P_0(x)*Q_1(x)) + P_0(x)*Q_0(x)$. Como el valor máximo de los coeficientes en todos los nuevos polinomios ahora es $\lfloor \sqrt{M} \rfloor$, entonces el valor máximo intermedio es $\approx nM$, es decir, en este caso es $\approx 10^{14}$, lo cual no pierde precisión.
- La segunda forma es usando NTT, para ello vamos a escoger tres primos distintos *NTT-friendly* grandes y aplicar teorema chino del residuo para recuperar la respuesta. Supongamos que los tres primos son $p_1$, $p_2$ y $p_3$, y que el módulo deseado es $M$. Entonces se debe cumplir que $p_1 p_2 p_3 > nM^2$.

## Operaciones sobre series de potencias
### Recíproco
Sea $P(x)$ una serie de potencias. Queremos hallar otra serie $Q(x)$ tal que $P(x)Q(x) = 1$.
- Ejemplo, si $P(x) = 1-x$, entonces $Q(x)=\dfrac{1}{P(x)}=\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \ldots$
- Ejemplo, si $P(x) = 1-x-x^2$, entonces $Q(x) = \dfrac{1}{1-x-x^2} = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + 21x^7 + \ldots$
- Ejemplo, si $P(x) = (1-x)^k$, entonces $Q(x) = \dfrac{1}{(1-x)^k} = \displaystyle \sum_{n=0}^{\infty} \binom{n+k-1}{k-1}x^n$.

De forma general, podemos usar la FFT/NTT para calcular el recíproco de una serie de potencias en $O(n \log n)$ usando un método similar a Newton-Rhapson.

#### Problema - [Solving the equation](https://omegaup.com/arena/problem/Solving-the-equation/)
Ejemplo, si queremos hallar el número de soluciones de la ecuación $\displaystyle \sum_{i=1}^{k} a_i x_i = n$, donde ya conocemos todos los valores $a_i$, podemos hacer lo siguiente:
- Vemos que para cada término de la suma $a_i x_i$ podemos colocar los valores $0, a_i, 2a_i, 3a_i, \ldots$, es decir, todos los múltiplos no negativos de $a_i$.
- Entonces, como $1 \leq a_i \leq 10$, primero podemos contar la frecuencia de cada $a_i$, digamos $cnt[x]$, donde $1 \leq x \leq 10$.
- Definamos a $P_j(x) = \displaystyle \sum_{i=0}^{\infty} x^{ij}$, entonces la respuesta es $Q(x) = \displaystyle \prod_{j=1}^{10} P_j(x) ^ {cnt[j]}$.
- Pero vemos que $P_j(x) = \dfrac{1}{1-x^j}$. Entonces, $Q(x) = \displaystyle \prod_{j=1}^{10} \dfrac{1}{(1-x^j)^{cnt[j]}} = \dfrac{1}{\displaystyle \prod_{j=1}^{10} (1-x^j)^{cnt[j]}}$. Podemos hallar cada $(1-x^j)^{cnt[j]}$ en complejidad $O(k)$ usando el triángulo de Pascal, luego los multiplicamos entre sí con FFT y finalmente obtenemos el recíproco.

#### Problema - [A Cumulative Sum Problem](https://www.spoj.com/problems/OVICUMSUM/)
Vemos que acumular un arreglo $a_i$ es equivalente a hallar todas sus sumas prefijo. Visto de otra forma, supongamos que $A_0(x) = a_0 + a_1x + a_2x^2 + \ldots$. Sea $A_k(x)$ el polinomio que representa el arreglo después de haberlo acumulado $k$ veces.

Veamos ahora cómo obtener las transiciones. Por ejemplo, $$ \begin{align*}
A_1(x) &= a_0 + (a_0 + a_1)x + (a_0 + a_1 + a_2)x^2 + (a_0 + a_1 + a_2 + a_3)x^3 + \ldots \\
&= a_0(1 + x + x^2 + x^3 + \ldots) + a_1(x + x^2 + x^3 + x^4 + \ldots) + a_2(x^2 + x^3 + x^4 + \ldots) + \ldots \\
&= a_0(1 + x + x^2 + x^3 + \ldots) + a_1 x (1 + x + x^2 + x^3 + \ldots) + a_2x^2(1 + x + x^2 + \ldots) + \ldots \\
&= (a_0 + a_1x + a_2x^2 + \ldots) (1 + x + x^2 + x^3 + \ldots) \\
&= \dfrac{A_0(x)}{1-x}
\end{align*}
$$

Es decir, $A_{k}(x) = A_{k-1}(x) \dfrac{1}{1-x}$, por lo tanto, $A_k(x) = \dfrac{A_0(x)}{(1-x)^k} = A_0(x) \left[ \displaystyle \sum_{n=0}^{\infty} \binom{n+k-1}{k-1}x^n \right]$.