---
tags: fft, ntt, polynomials, newton-raphson, inverse, square-root, logarithm, exponential, taylor-series, divide-and-conquer, power-series, generating-functions
---

# Operaciones con polinomios
## Método de Newton-Raphson
Sea $f(x)$ una función a la cual queremos hallarle sus raíces, es decir, qué valores de $x$ hacen que $f(x)=0$. Por ejemplo, si $f(x)=x^2-a$, entonces una raíz es $x=\sqrt{a}$.

El algoritmo funciona de la siguiente manera:
- Proponemos un valor inicial $x_0$ que esté cercano a la raíz que queremos encontrar.
- Hacemos la iteración $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ para refinar el valor anterior de $x_n$ y que vaya convergiendo cada vez más a la raíz buscada.
- Repetimos el paso anterior hasta que lleguemos a la precisión deseada.

Por ejemplo, si $f(x)=x^2-a$, entonces $f'(x)=2x$, y las iteraciones quedan como:
$$
x_{n+1} = x_{n} - \dfrac{x_n^2-a}{2x_n} = \dfrac{2x_n^2-(x_n^2-a)}{2x_n} = \dfrac{x_n^2+a}{2x_n}
$$

Podemos hallar la raíz $k$-ésima usando este mismo método, simplemente cambiamos $f(x)$ a $f(x)=x^k-a$, entonces $f'(x)=kx^{k-1}$ y la iteración es:
$$
x_{n+1} = x_{n} - \dfrac{x_n^k-a}{kx_n^{k-1}} = \dfrac{(k-1)x_n^k+a}{kx_n^{k-1}}
$$

Ahora supongamos que tenemos una función $F(P)$, donde $P$ es un polinomio. Podemos adaptar este método para hallar el polinomio que cumpla que $F(P)=0$.

Por ejemplo, si $F(P)=P^k-A$, entonces al hacer $F(P)=0$ hallaremos un $P$ tal que $P^k-A=0$, o sea, $P=\sqrt[k]{A}$. Resulta que también podemos usar el método de Newton para ir hallando de forma iterativa los coeficientes de $P$:
- Tenemos que proponer un polinomio inicial de grado cero $P_0$ tal que $P_0=p_0$, donde $p_0$ sea correcto.
- En la $n$-ésima iteración ($n \geq 1$), hacemos $P_n \equiv P_{n-1} - \dfrac{F(P_{n-1})}{F'(P_{n-1})} \mod{x^{2^n}}$. Vemos que en cada iteración se duplica el número correcto de coeficientes de $P$.

### Inverso multiplicativo
Supongamos que queremos hallar el inverso multiplicativo de una serie de potencias $A(x)$ dada por $A(x)=a_0+a_1x+a_2x^2+\cdots$.

Sea $F(P) = A - \dfrac{1}{P}$, entonces $F(P)=0$ implica que $P=\dfrac{1}{A}$, que es justo lo que queremos. Tenemos que $F'(P)=\dfrac{1}{P^2}$, y las iteraciones quedan como:
$$
\begin{align}
P_n &\equiv P_{n-1} - \dfrac{A-\frac{1}{P_{n-1}}}{\frac{1}{P_{n-1}^2}} &\mod{x^{2^n}} \\
&\equiv P_{n-1}-P_{n-1}^2 \left( A-\frac{1}{P_{n-1}} \right) &\mod{x^{2^n}} \\
&\equiv P_{n-1} - P_{n-1}^2 A + P_{n-1} &\mod{x^{2^n}} \\
&\equiv 2P_{n-1} - P_{n-1}^2 A &\mod{x^{2^n}}
\end{align}
$$

El término inicial $a_0$ tiene que cumplir que $a_0 - \frac{1}{p_0} = 0$, es decir, $p_0 = \frac{1}{a_0}$. De aquí vemos que $P(x)$ existe si y solo si $a_0 \neq 0$.

Sea $T(n)$ complejidad de hallar el inverso de $A$ con $n$ coeficientes de precisión. Tenemos que $T(n)=T(n/2) + O(n \log n)$, pues necesitamos primero el inverso con precisión $n/2$ y de acuerdo a la recurrencia de la iteración, requerimos una multiplicación con polinomios de tamaño $n$, la cual podemos hacer con FFT con complejidad de $O(n \log n)$. Resolviendo la recurrencia, tenemos que $T(n) = O(n \log n)$.

### Raíz cuadrada
Ahora hallemos $\sqrt{A(x)}$.

Sea $F(P)=P^2-A$, para hallar el primer término $p_0$ necesitamos que $p_0^2=a_0$, es decir, $p_0=\sqrt{a_0}$. Después procedemos con las iteraciones:
$$
\begin{align}
P_n &\equiv \dfrac{P_{n-1}^2+A}{2P_{n-1}} &\mod{x^{2^n}} \\
&\equiv \dfrac{1}{2} \left( P_{n-1} + \dfrac{A}{P_{n-1}} \right) &\mod{x^{2^n}}
\end{align}
$$
Vemos que para hallar $\dfrac{A}{P_{n-1}}$, tenemos que usar el inverso de $P_{n-1}$, que es justo la operación que vimos antes.

Si los coeficientes de $A$ pertenecen a un campo finito módulo $p$, es decir, $a_i \in \mathbb{F}_p$, necesitamos garantizar que la raíz cuadrada de $a_0$ exista y sea distinta de cero.

La complejidad es $O(n \log n)$.

### Logaritmo
Ahora vamos a hallar el logaritmo natural de $A(x)$, y le vamos a llamar $\ln(A)$. Dicho logaritmo cumplirá todas las propiedades de un logaritmo ordinario en los números reales.

Sea $P(x)=\ln(A(x))$, entonces al derivar ambos lados respecto de $x$ obtenemos $P'(x) = \dfrac{A'(x)}{A(x)}$. Finalmente, integramos ambos lados respecto a $x$ y obtenemos:
$$
P(x) = \int \dfrac{A'(x)}{A(x)} dx
$$

Si los coeficientes de $A$ pertenecen a un campo finito, entonces requerimos que $a_0=1$, pues tenemos que $\ln(A) = \ln(a_0 + a_1x + a_2x^2 + \cdots) = \ln\left(a_0\left(1+\frac{a_1}{a_0}x + \frac{a_2}{a_0}x^2+\cdots\right)\right) = \ln(a_0) + \ln\left(1+\frac{a_1}{a_0}x + \frac{a_2}{a_0}x^2+\cdots\right)$, y $\ln(a_0)$ no está definido en un campo finito, a menos que $a_0=1$, pues $\ln(1)=0$ y el $0$ sí existe.

### Exponencial
Vamos a hallar la exponencial de $A(x)$, y le vamos a llamar $\exp(A)$ o $e^A$.

Sea $F(P) = A-\ln(P)$, entonces $F(P)=0$ implica que $P=\exp(A)$, que es justo lo que queremos.

Tenemos que $F'(P) = -\dfrac{1}{P}$, y las iteraciones quedan como:
$$
\begin{align}
P_n &\equiv P_{n-1} - \dfrac{A-\ln(P_{n-1})}{-\frac{1}{P_{n-1}}} &\mod{x^{2^n}} \\
&\equiv P_{n-1}+P_{n-1}(A-\ln(P_{n-1})) &\mod{x^{2^n}} \\
&\equiv P_{n-1}(1+A-\ln(P_{n-1})) &\mod{x^{2^n}}
\end{align}
$$

Si los coeficientes de $A$ pertenecen a un campo finito, entonces requerimos que $a_0=0$, pues tenemos que $e^A = e^{a_0+a_1x+a_2x^2+\cdots} = e^{a_0}e^{a_1x+a_2x^2+\cdots}$, y $e^{a_0}$ no está definido en un campo finito, a menos que $a_0=0$, pues $e^0=1$ y el $1$ sí existe. De hecho, el término inicial de $P$ sería entonces $p_0=e^{a_0}=1$.

### $k$-ésima potencia de una serie de potencias
Usando la exponencial y el logaritmo, podemos hallar $[A(x)]^k$ con una complejidad que no depende de $k$. Por ahora supongamos que $a_0=1$. Sea $P=A^k$, si tomamos logaritmo a ambos lados obtenemos $\ln(P)=\ln(A^k)=k\ln(A)$, entonces $P=\exp(k\ln(A))$.

En el caso general cuando $a_0 \neq 1$, podemos representar a $A(x)$ de forma única como $A(x)=\alpha x^t B(x)$, donde $\alpha$ es el primer coeficiente distinto de cero en $A(x)$, $t$ es la mínima posición en donde aparece y $B(x)$ es otra serie de potencias ya ahora sí con $b_0=1$. Entonces, $P=A^k=\alpha^k x^{kt} \exp(k \ln(B))$.

Aquí $k$ ni siquiera necesita ser un número entero. Por ejemplo, si $k=\frac{1}{2}$, obtenemos un método adicional para hallar la raíz cuadrada de $A$.

Por ejemplo, si $A(x)=3x^2+6x^3+7x^4+10x^5$, entonces $A(x)=\underbrace{3}_{\alpha} \underbrace{x^2}_{x^t} (\underbrace{1+2x+(7/3)x+(10/3)x^2}_{B(x)})$.

### Cociente y residuo
Sean $A(x)$ y $B(x)$ dos polinomios de grados $n$ y $m$ respectivamente. Queremos hallar otros dos polinomios $Q(x)$ y $R(x)$ tales que $A(x) = B(x)Q(x) + R(x)$, donde $deg(R) < deg(B)$. Es decir, una generalización al algoritmo de la división, en donde dividimos $A(x)$ entre $B(x)$ para obtener un cociente $Q(x)$ y un residuo $R(x)$.

Supongamos que $n \geq m$ (en otro caso el cociente es $Q(x)=0$ y el residuo es $R(x)=A(x)$), entonces $deg(Q)=n-m$. Sean $A^R(x)$ y $B^R(x)$ los polinomios $A(x)$ y $B(x)$ con los coeficientes en reversa, es decir:
$$
\begin{align}
A^R(x) &= x^n A(1/x) = a_n + a_{n-1}x + \cdots + a_0 x^n \\
B^R(x) &= x^m B(1/x) = b_m + b_{m-1}x + \cdots + b_0 x^m
\end{align}
$$

Ahora veamos cómo queda el cociente $Q(x)$ de reversa:
$$
\begin{align}
Q^R(x) &= x^{n-m} Q(1/x) = q_{n-m} + q_{n-m+1}x + \cdots + q_0 x^{n-m}
\end{align}
$$

De la ecuación principal $A(x)=B(x)Q(x)+R(x)$, reverseamos ambos lados y obtenemos:
$$
\begin{align}
A^R(x) &= (B(x)Q(x) + R(x))^R \\
&= x^n(B(1/x)Q(1/x) + R(1/x)) \\
&= x^m B(1/x)x^{n-m}Q(1/x) + x^nR(1/x) \\
&= B^R(x)Q^R(x) + x^n \left(r_0 + r_1 x^{-1} + \cdots + r_{deg(R)}x^{-deg(R)} \right) \\
&= B^R(x)Q^R(x) + \left(r_0 x^n + r_1 x^{n-1} + \cdots + r_{deg(R)}x^{n-deg(R)} \right)
\end{align}
$$

El polinomio entre paréntesis tiene como mínima potencia de $x$ a $n-deg(R)$, y como $deg(R) < m$, entonces $n-deg(R) > n-m$, es decir, tiene potencias únicamente mayores o iguales a $n-m+1$. Por lo tanto, si tomamos ambos lados de la última igualad módulo $x^{n-m+1}$, vamos a cancelar ese polinomio entre paréntesis, y nos quedamos con:
$$
A^R(x) \equiv B^R(x)Q^R(x) \mod x^{n-m+1}
$$

Y de ahí podemos despejar $Q^R(x)$ usando el inverso multiplicativo de $B^R(x)$, que ya sabemos cómo calcular:
$$
Q^R(x) \equiv \dfrac{A^R(x)}{B^R(x)} \mod x^{n-m+1}
$$

Finalmente, teniendo $Q^R(x)$ lo podemos reversear de nuevo y obtener $Q(x)$, y para hallar $R(x)$ simplemente lo despejamos: $R(x)=A(x)-B(x)Q(x)$. La complejidad de todo esto sigue siendo $O(n \log n)$.

## Series de potencias famosas y series de Taylor
- $\exp(x) = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots$
- $\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots$
- $\dfrac{1}{1+x} = 1 - x + x^2 - x^3 + \cdots$
- $\ln(1+x) = x - \dfrac{x^2}{2} + \dfrac{x^3}{3} - \dfrac{x^4}{4} + \cdots$
- $\ln(1-x) = -x - \dfrac{x^2}{2} - \dfrac{x^3}{3} - \dfrac{x^4}{4} - \cdots$
- $\displaystyle (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$ , $\quad n \in \mathbb{N}$
- $\displaystyle (1+x)^\alpha = 1 + \dfrac{\alpha}{1!} x + \dfrac{\alpha(\alpha-1)}{2!} x^2 + \dfrac{\alpha(\alpha-1)(\alpha-2)}{3!} x^3 + \cdots$ , $\quad \alpha \in \mathbb{R}$
- $\displaystyle \dfrac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$ , $\quad k \in \mathbb{N}$

## Problemas
### [Subset sum](https://judge.yosupo.jp/problem/sharp_p_subset_sum)
:::spoiler **Descripción**
Dados $N$ ($N \leq 10^6$) enteros positivos $s_0, s_1, \ldots, s_{N-1}$ y un entero positivo $T$ ($T \leq 5 \times 10^5$, $s_i \leq T$), determinar de cuántas maneras podemos escoger algunos valores $s_i$ tales que su suma es $t$, para cada $t=1,2,\ldots,T$. Dos maneras son distintas si los conjuntos de los índices de las $s_i$'s escogidas en cada manera son diferentes.
:::

:::spoiler **Ejemplo**
Si $S=[1,1,2,2,3]$ y $T=3$, entonces:
- Para $t=1$ hay 2 formas: $s_0 = s_1 = 1$
- Para $t=2$ hay 3 formas: $s_0+s_1 = s_2 = s_3 = 2$
- Para $t=3$ hay 5 formas: $s_0+s_2 = s_0+s_3 = s_1+s_2 = s_1+s_3 = s_4 = 3$

Entonces la respuesta es $[2,3,5]$.
:::

:::spoiler **Solución**
Sea $\displaystyle F(x) = \prod_{i=0}^{N-1} (1+x^{s_i})$, donde el coeficiente de $x^t$ en $F(x)$ es la respuesta para cada $t$. Tomemos logaritmo a ambos lados:
$$
\begin{align}
\ln(F) &= \ln \left( \prod_{i=0}^{N-1} (1+x^{s_i}) \right) \\
&= \sum_{i=0}^{N-1} \ln(1+x^{s_i}) \\
&= \sum_{i=0}^{N-1} \sum_{j=1}^{\infty} \dfrac{(x^{s_i})^j}{j} (-1)^{j-1} \\
&= \sum_{j=1}^{\infty} \dfrac{(-1)^{j-1}}{j} \sum_{i=0}^{N-1} x^{s_i j}
\end{align}
$$

Si suponemos que todas las $s$'s son distintas, entonces podemos hallar la suma anterior con una complejidad de $T+T/2+T/3+\cdots+T/T = O(T \log T)$. Si hay $s$'s repetidas, simplemente calculamos la frecuencia de cada elemento y la tomamos en cuenta en la suma:
$$
\ln(F) = \sum_{j=1}^{\infty} \dfrac{(-1)^{j-1}}{j} \sum_{i=1}^{T} x^{i j} freq[i]
$$
Finalmente, tomamos la exponencial a ambos lados:
$$
F(x) = \exp\left(\sum_{j=1}^{\infty} \dfrac{(-1)^{j-1}}{j} \sum_{i=1}^{T} x^{i j} freq[i]\right)
$$
Por lo tanto, la complejidad total queda como $O(T \log T)$.
:::

### [Progresión aritmético-geométrica finita](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial)

### [Progresión aritmético-geométrica infinita](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial_limit)

### [Linear Diophantine Equation](https://www.spoj.com/problems/COUNTDIO/)
:::spoiler **Descripción**
Hallar el número de soluciones en los enteros no negativos de la ecuación $a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = m$, donde:
- $1 \leq n \leq 6 \times 10^4$
- $1 \leq m \leq 10^{18}$
- $1 \leq a_i \leq 6 \times 10^4$
- $1 \leq a_1 + a_2 + \cdots + a_n \leq 6 \times 10^4$
:::

:::spoiler **Ejemplo**
Si la ecuación es $a_1+2a_2=6$, tenemos 4 soluciones, que son $(0,3)$, $(2,2)$, $(4,1)$ y $(6,0)$.
:::

:::spoiler **Solución**

:::

### [Particiones de un entero](https://judge.yosupo.jp/problem/partition_function)
:::spoiler **Descripción**
Sea $p(n)$ el número de formas de escribir el entero positivo $n$ como una suma de enteros positivos, sin importar el orden. Hallar $p(n)$ para $n=0,1,2,\ldots,N$ ($N \leq 5 \times 10^5$).
:::

:::spoiler **Ejemplo**
Si $n=4$, lo podemos escribir de 5 maneras como:
- $4 = 1+1+1+1$
- $4 = 1+1+2$
- $4 = 1+3$
- $4 = 2+2$
- $4 = 4$

Por lo tanto, $p(4)=5$.
:::

:::spoiler **Solución**
Podemos representar cada partición de $n$ de forma única con la frecuencia de sus sumandos. Es decir, hay que resolver la ecuación $x_1 + 2x_2 + 3x_3 + \cdots + nx_n = n$, donde $x_i$ es la frecuencia del sumando $i$, y $x_i \geq 0$. El número de soluciones es entonces igual a $p(n)$.

Por cada sumando, propongamos un polinomio que represente a todos los posibles valores que podemos colocar ahí, entonces al multiplicarlos todos nos fijamos en el coeficiente de $x^n$, y eso será igual a $p(n)$. Es decir:
$$
\begin{align}
F(x) &= \prod_{i=1}^{n} (1+x^i+x^{2i}+x^{3i}+\cdots) \\
&= \prod_{i=1}^{n} \dfrac{1}{1-x^i}
\end{align}
$$

Tomamos logaritmo a ambos lados:
$$
\begin{align}
\ln(F) &= \sum_{i=1}^{n} \ln\left(\dfrac{1}{1-x^i}\right) \\
&= -\sum_{i=1}^{n} \ln(1-x^i) \\
&= \sum_{i=1}^{n} \sum_{j=1}^{\infty} \dfrac{(x^i)^j}{j} \\
&= \sum_{j=1}^{\infty} \dfrac{1}{j} \sum_{i=1}^{n} x^{ij}
\end{align}
$$

Finalmente, tomamos la exponencial a ambos lados:
$$
F(x) = \exp\left( \sum_{j=1}^{\infty} \dfrac{1}{j} \sum_{i=1}^{n} x^{ij} \right)
$$

La complejidad total es entonces $O(n \log n)$.
:::

### [Sum of Fibonacci Sequence](https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_g)
:::spoiler **Descripción**
Sea $f_n$ la sucesión de Fibonacci, donde $f_0=0$, $f_1=1$ y $f_k=f_{k-1}+f_{k-2}$ para $k \geq 2$.

Definimos las sucesiones $g_1, g_2, \ldots, g_n$ como:
- $g_{1,j} = f_j$
- Para $i \geq 2$: $\displaystyle g_{i,j} = \sum_{k=0}^{j} g_{i-1, k}$

Hallar $g_{n,m}$ ($1 \leq n \leq 2 \times 10^5$, $1 \leq m \leq 10^{18}$).
:::

:::spoiler **Ejemplo**
Si $n=4$ y $m=6$, podemos ver las suceciones $d_i$ en la siguiente tabla:
| | $d_{i,0}$ | $d_{i,1}$ | $d_{i,2}$ | $d_{i,3}$ | $d_{i,4}$ | $d_{i,5}$ | $d_{i,6}$ |
| - | - | - | - | - | - | - | - |
| $d_1$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
| $d_2$ | 0 | 1 | 2 | 4 | 7 | 12 | 20 |
| $d_3$ | 0 | 1 | 3 | 7 | 14 | 26 | 46 |
| $d_4$ | 0 | 1 | 4 | 11 | 25 | 51 | 97 |

Por lo tanto, $d_{4,6}=97$.
:::

:::spoiler **Solución**

:::

### [Parity Party](https://www.hackerrank.com/challenges/parity-party/problem)
:::spoiler **Descripción**
Tenemos $n$ dulces ++etiquetados++ del $1$ al $n$ ($1 \leq n \leq 10^9$), los cuales queremos repartir entre todas las personas de una fiesta. En la fiesta hay tres tipos de personas:
- $a$ personas quieren recibir un número impar de dulces.
- $b$ personas quieren recibir un número par de dulces.
- $c$ personas quieren recibir cualquier cantidad de dulces.

Hallar el número de formas de dividir los $n$ dulces entre todas las $a+b+c$ personas ($1 \leq a+b+c$, $0 \leq a,b,c \leq 5 \times 10^4$), tal que todas estén satisfechas.
:::

:::spoiler **Ejemplo**
Si $a=1$, $b=1$, $c=0$ y $n=3$, tenemos 3 dulces, digamos que son $d_1$, $d_2$ y $d_3$. Hay 4 maneras de repartirlos entre las 2 personas:
| | Persona 1° (impar) | Persona 2° (par) |
| - | - | - |
| 1° | $\{d_1\}$ | $\{d_2, d_3\}$ |
| 2° | $\{d_2\}$ | $\{d_1, d_3\}$ |
| 3° | $\{d_3\}$ | $\{d_1, d_2\}$ |
| 4° | $\{d_1, d_2, d_3\}$ | $\{\}$ |

Notemos la diferencia entre dulces etiquetados y no etiquetados:
- En el caso no etiquetado solo nos importa la cantidad de dulces que recibe cada persona (todos los dulces son indistinguibles).
- En el caso etiquetado nos importa la cantidad de dulces que recibe cada persona y qué dulces recibe (todos los dulces son distintos a pares).

Si el problema trabajara con dulces no etiquetados, la respuesta para este ejemplo sería 2:
| | Persona 1° (impar) | Persona 2° (par) |
| - | - | - |
| 1° | 1 dulce | 2 dulces |
| 2° | 3 dulces | 0 dulces |
:::

:::spoiler **Solución**

Primero resolvamos la versión no etiquetada. Tenemos una ecuación de la siguiente forma: $(x_1 + x_2 + \cdots + x_a) + (y_1 + y_2 + \cdots + y_b) + (z_1 + z_2 + \cdots + z_c) = n$, donde cada incógnita representa a una persona. Las restricciones son que las $x_i$ son impares, las $y_i$ son pares y las $z_i$ no tienen restricción adicional. Entonces el problema se reduce a hallar el número de soluciones de dicha ecuación.

Sea $X(z) = z + z^3 + z^5 + \cdots = \dfrac{z}{1-z^2}$, $Y(z)=1+z^2+z^4+ \cdots = \dfrac{1}{1-z^2}$, $Z(z) = 1+z+z^2+z^3+\cdots = \dfrac{1}{1-z}$. Sea $F(z)$ la función generadora de la respuesta, entonces $F(z)=[X(z)]^a [Y(z)]^b [Z(z)]^c = \dfrac{z^a}{(1-z^2)^{a+b}(1-z)^c}$, y la respuesta estará en el coeficiente de $z^n$ de $F(z)$.

Regresando al problema sí etiquetado, vemos que por cada solución no etiquetada, podemos generar varias soluciones etiquetadas. Las vamos a generar hallando todas las posibles formas de repartir los dulces entre las personas. Supongamos que tenemos una solución particular $(x'_1, x'_2, \ldots, x'_a, y'_1, y'_2, \ldots, y'_b, z'_1, z'_2, \ldots, z'_c)$. Entonces, el número de soluciones etiquetadas es igual al coeficiente multinomial $\displaystyle \binom{n}{x'_1, x'_2, \ldots, x'_a, y'_1, y'_2, \ldots, y'_b, z'_1, z'_2, \ldots, z'_c}$, por lo tanto hay que modificar las funciones $X(z)$, $Y(z)$ y $Z(z)$.

Quedan de la siguiente manera:
$$
\begin{align}
X(z) &= \dfrac{1}{1!}z + \dfrac{1}{3!}z^3 + \dfrac{1}{5!}z^5 + \cdots = \sinh(z) = \dfrac{e^z - e^{-z}}{2} \\
Y(z) &= \dfrac{1}{0!} + \dfrac{1}{2!}z^2 + \dfrac{1}{4!}z^4 + \cdots = \cosh(z) = \dfrac{e^z + e^{-z}}{2} \\
Z(z) &= \dfrac{1}{0!} + \dfrac{1}{1!}z + \dfrac{1}{2!}z^2 + \cdots = e^z
\end{align}
$$

En el caso de ejemplo, vemos que queremos el coeficiente de $z^3$ multiplicado por $3!$ de $X(z)Y(z)$, que es igual a $\displaystyle \dfrac{3!}{1! \cdot 2!} + \dfrac{3!}{3! \cdot 0!} = \binom{3}{1} + \binom{3}{3} = 4$.

De forma general, quiero el coeficiente de $z^n$ multiplicado por $n!$ de $G(z)=[X(z)]^a [Y(z)]^b [Z(z)]^c$. Eso es igual a:
$$
\begin{align}
G(z) &= \left( \dfrac{e^z - e^{-z}}{2} \right)^a \left( \dfrac{e^z + e^{-z}}{2} \right)^b (e^z)^c \\
&= \left( \dfrac{e^z - 1/e^z}{2} \right)^a \left( \dfrac{e^z + 1/e^z}{2} \right)^b (e^z)^c \\
&= \left( \dfrac{e^{2z} - 1}{2e^z} \right)^a \left( \dfrac{e^{2z} + 1}{2e^z} \right)^b (e^z)^c \\
&= \dfrac{(e^{2z}-1)^a (e^{2z}+1)^b (e^z)^c}{2^{a+b}(e^z)^{a+b}} \\
&= \dfrac{(e^{2z}-1)^a (e^{2z}+1)^b (e^z)^{c-a-b}}{2^{a+b}}
\end{align}
$$

Sea $t=e^z$, entonces $G(z) = \dfrac{(t^2-1)^a (t^2+1)^b t^{c-a-b}}{2^{a+b}}$. Hallemos $(t^2-1)^a$ y $(t^2+1)^b$ con coeficiente binomial y los multiplicamos con NTT. Entonces, $(t^2-1)^a (t^2+1)^b = \sum_{k=0}^{2(a+b)} p_k t^k$, por lo tanto:
$$
\begin{align}
G(z) &= \dfrac{\sum_{k=0}^{2(a+b)} p_k t^k t^{c-a-b}}{2^{a+b}} \\
&= \dfrac{\sum_{k=0}^{2(a+b)} p_k t^{k+c-a-b}}{2^{a+b}} \\
&= \dfrac{\sum_{k=0}^{2(a+b)} p_k e^{(k+c-a-b)z}}{2^{a+b}}
\end{align}
$$

Por serie de Taylor, sabemos que $e^{\alpha z} = 1 + \alpha z + \dfrac{\alpha^2}{2!}z^2 + \dfrac{\alpha^3}{3!}z^3 + \cdots$, de donde vemos que el coeficiente de $z^n$ es $\dfrac{\alpha^n}{n!}$. Por lo tanto, como $G(z)$ es una suma de exponenciales, por cada una tomamos el coeficiente de $z^n$, sin olvidar multiplicar al final por $n!$:
$$
\begin{align}
ans &= n! \cdot \dfrac{\sum_{k=0}^{2(a+b)} p_k (k+c-a-b)^n / n!}{2^{a+b}} \\
&= \dfrac{\sum_{k=0}^{2(a+b)} p_k (k+c-a-b)^n}{2^{a+b}}
\end{align}
$$

Al final, tenemos una complejidad de $O((a+b)\log(a+b) + (a+b)\log(n))$.

:::

### [The Child and Binary Tree](https://codeforces.com/problemset/problem/438/E)
:::spoiler **Descripción**
Definimos al *peso* de un árbol binario como la suma de los pesos de todos sus nodos. Determinar, para cada $s=1,2,\ldots,m$, cuántos árboles binarios existen con peso igual a $s$, donde los pesos de los nodos los tomaremos de un conjunto dado de $n$ enteros positivos distintos $\{c_1,c_2,\ldots,c_n\}$. Los límites son $1 \leq n, m, c_i \leq 10^5$.
:::

:::spoiler **Ejemplo**
Si $m=3$ y el conjunto de pesos posibles es $\{1,2\}$, tenemos los siguientes árboles:
- Para $s=1$, solo tenemos 1 árbol:
- Para $s=2$, tenemos 3 árboles:
- Para $s=3$, tenemos 9 árboles:

:::

:::spoiler **Solución**
Primero resolvamos un problema más sencillo: determinar cuántos árboles binarios existen con $k$ nodos. Sea $C_k$ dicho conteo, tenemos que $C_0=1$ y tenemos la recurrencia:
$$
\begin{align}
C_k &= C_0 C_{k-1} + C_1 C_{k-2} + C_2 C_{k-3} + \cdots + C_{k-1} C_0 \\
&= \sum_{i=0}^{k-1} C_i C_{k-1-i}
\end{align}
$$

Dicha recurrencia funciona, pues para construir un árbol de $k$ nodos, podemos colocar 1 nodo como raíz y redistribuir los $k-1$ nodos restantes de las siguientes maneras:
- Un subárbol de $0$ nodos del lado izquierdo y un subárbol de $k-1$ nodos del lado derecho.
- Un subárbol de $1$ nodos del lado izquierdo y un subárbol de $k-2$ nodos del lado derecho.
- ...
- Un subárbol de $k-1$ nodos del lado izquierdo y un subárbol de $0$ nodos del lado derecho.

Hallemos la función generadora de la sucesión $C_k$, es decir, $F(x)=C_0 + C_1x + C_2x^2 + C_3x^3 + \cdots$. Vemos que el coeficiente de $x^k$ nos dice el valor de $C_k$. Vamos a obtener una fórmula cerrada para $F(x)$, para ello vamos a sustituir la definición de cada $C_k$:
$$
\begin{align}
F(x) &= 1 + (C_0 C_0)x + (C_0 C_1 + C_1 C_0)x^2 + (C_0 C_2 + C_1 C_1 + C_2 C_0)x^3 + \cdots
\end{align}
$$

Vemos que los coeficientes se parecen a una convolución de la secuencia $C_k$ con ella misma. Veamos a qué es igual $F(x)^2$:
$$
\begin{align}
F(x)^2 &= C_0 C_0 + (C_0 C_1 + C_1 C_0)x + (C_0 C_2 + C_1 C_1 + C_2 C_0)x^2 + \cdots
\end{align}
$$

Relacionando ambas igualdades, tenemos que:
$$
\begin{align}
F(x) &= 1 + x(C_0 C_0 + (C_0 C_1 + C_1 C_0)x + (C_0 C_2 + C_1 C_1 + C_2 C_0)x^2 + \cdots) \\
&= 1 + xF(x)^2
\end{align}
$$

Por lo tanto, tenemos que $F(x)=1+xF(x)^2$, reacomodamos: $xF(x)^2 - F(x) + 1 = 0$ y despejamos $F(x)$:
$$
F(x) = \dfrac{1 \pm \sqrt{1 - 4x}}{2x}
$$
Tenemos dos posibles elecciones para el signo $\pm$ pero solo una de ellas va a funcionar. Sabemos que el término constante de $F(x)$ es $1$, entonces escogamos el signo tal que eso siga siendo cierto. La elección correcta es usar el signo negativo, por lo tanto:
$$
F(x) = \dfrac{1 - \sqrt{1 - 4x}}{2x}
$$

Ahora, regresando al problema original, tomemos un árbol binario cualquiera con $k$ nodos, y debemos colocarle a cada nodo un peso. Es decir, los pesos ahora son los sumandos, y por cada uno podemos ponerle los pesos del conjunto $\{c_1, c_2, \ldots, c_n\}$. Sea $A(x)=\sum_{i=1}^{n} x^{c_i}$. Por ejemplo, en el caso de ejemplo $A(x)=x+x^2$.

Sabemos que tenemos $C_k$ árboles binarios distintos, y necesitamos asignarle pesos a cada uno. La función generadora que nos dirá eso es $C_k A(x)^k$, y finalmente necesitamos sumar eso para todos los posibles tamaños de árbol. Sea $G(x)$ dicha función generadora, tenemos que:
$$
\begin{align}
G(x) &= \sum_{k=0}^{\infty} C_k [A(x)]^k \\
&= F(A(x)) \\
&= \dfrac{1 - \sqrt{1 - 4A(x)}}{2A(x)}
\end{align}
$$

Y la respuesta para cada $s$ la encontramos en el coeficiente de $x^s$ de $G(x)$. Sin embargo, el inverso multiplicativo de $A(x)$ no existe, por lo que hay que simplifcar la expresión racionalizando el numerador:
$$
\begin{align}
G(x) &= \dfrac{1 - \sqrt{1 - 4A(x)}}{2A(x)} \cdot \dfrac{1 + \sqrt{1 - 4A(x)}}{1 + \sqrt{1 - 4A(x)}} \\
&= \dfrac{1-(1-4A(x))}{2A(x)\left(1 + \sqrt{1 - 4A(x)}\right)} \\
&= \dfrac{4A(x)}{2A(x)\left(1 + \sqrt{1 - 4A(x)}\right)} \\
&= \dfrac{2}{1 + \sqrt{1 - 4A(x)}}
\end{align}
$$

La complejidad al final queda como $O(m \log m)$, pues necesitamos truncar todos los polinomios para obtener las $m$ respuestas que necesitamos.

:::

:::spoiler **Extra**
Podemos obtener la fórmula no recursiva para $C_k$ ($k$--ésimo número de Catalán) a partir de su función generadora:
$$
\begin{align}
F(x) &= \dfrac{1}{2x} \left(1 - \sqrt{1-4x} \right) \\
&= \dfrac{1}{2x} \left[ 1 - \left( 1 + \dfrac{\frac{1}{2}}{1!}(-4x) + \dfrac{\frac{1}{2}(\frac{1}{2}-1)}{2!}(-4x)^2 + \dfrac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)}{3!}(-4x)^3 + \dfrac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)(\frac{1}{2}-3)}{4!}(4x)^4 + \cdots \right) \right] \\
&= \dfrac{1}{2x} \left[ \dfrac{\frac{1}{2}}{1!}(4x) - \dfrac{\frac{1}{2}(\frac{1}{2}-1)}{2!}(4x)^2 + \dfrac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)}{3!}(4x)^3 + \dfrac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)(\frac{1}{2}-3)}{4!}(4x)^4 + \cdots \right] \\
&= \dfrac{1}{2x} \left[ \dfrac{4^1}{2^1 \times 1!}x + \dfrac{1 \times 4^2}{2^2 \times 2!}x^2 + \dfrac{1 \times 3 \times 4^3}{2^3 \times 3!}x^3 + \dfrac{1 \times 3 \times 5 \times 4^4}{2^4 \times 4!}x^4 + \cdots \right] \\
&= \dfrac{1}{2x} \left[ \dfrac{2^1}{1!}x + \dfrac{1 \times 2^2}{2!}x^2 + \dfrac{1 \times 3 \times 2^3}{3!}x^3 + \dfrac{1 \times 3 \times 5 \times 2^4}{4!}x^4 + \cdots \right] \\
&= \dfrac{2^0}{1!} + \dfrac{1 \times 2^1}{2!}x + \dfrac{1 \times 3 \times 2^2}{3!}x^2 + \dfrac{1 \times 3 \times 5 \times 2^3}{4!}x^3 + \cdots \\
&= \dfrac{2^0}{1!} + \dfrac{1 \times 2 \times 2^1}{2 \times 2!}x + \dfrac{1 \times 2 \times 3 \times 4 \times 2^2}{2 \times 4 \times 3!}x^2 + \dfrac{1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 2^3}{2 \times 4 \times 6 \times 4!}x^3 + \cdots \\
&= \dfrac{2^0}{1!} + \dfrac{1 \times 2 \times 2^1}{1 \times 2^1 \times 2!}x + \dfrac{1 \times 2 \times 3 \times 4 \times 2^2}{1 \times 2 \times 2^2 \times 3!}x^2 + \dfrac{1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 2^3}{1 \times 2 \times 3 \times 2^3 \times 4!}x^3 + \cdots \\
&= \dfrac{0!}{0! \times 1!} + \dfrac{2!}{1! \times 2!}x + \dfrac{4!}{2! \times 3!}x^2 + \dfrac{6!}{3! \times 4!}x^3 + \cdots \\
&= \sum_{k=0}^{\infty} \dfrac{(2k)!}{k!(k+1)!} x^k
\end{align}
$$

Por lo tanto, $\displaystyle C_k = \dfrac{(2k)!}{k!(k+1)!} = \dfrac{1}{k+1} \binom{2k}{k}$.
:::

### Número de grafos conexos etiquetados
:::spoiler **Descripción**
Determinar cuántos grafos simples no dirigidos con $n$ nodos etiquetados existen tal que sean conexos. $n \leq 10^5$
:::

:::spoiler **Ejemplo**
Para $n=3$ tenemos 4 grafos posibles:

:::

:::spoiler **Solución**
Sea $d_n$ el número de grafos en $n$ nodos, no necesariamente conexos. Tenemos $\binom{n}{2}$ aristas posibles, y por cada una podemos decidir si la tomamos o no en el grafo, es decir, $d_n = 2^{n(n-1)/2}$.

Sea $c_n$ el número de grafos en $n$ nodos conexos. Intentemos contar el número total de grafos en términos de los grafos conexos: fijemos un vértice $v$ cualquiera del grafo, si la componente conexa que contiene a $v$ tiene $k$ vértices, entonces hay $\binom{n-1}{k-1}$ maneras de escoger los otros $k-1$ vértices de esa componente. Ya teniendo esto, hay $c_k$ formas de poner las aristas en esta componente conexa, y $d_{n-k}$ formas de poner las aristas en el resto del grafo. Si consideramos todos los tamaños para la componente conexa desde $k=1$ hasta $k=n$, tenemos que:

$$
\begin{align}
d_n &= \sum_{k=1}^{n} \binom{n-1}{k-1} c_k d_{n-k}
\end{align}
$$

Para hallar $c_n$ en términos de $d$ y posiblemente en términos de $c$'s anteriores, sacamos el último término de la suma y lo despejamos:
$$
\begin{align}
d_n &= \sum_{k=1}^{n-1} \binom{n-1}{k-1} c_k d_{n-k} + \binom{n-1}{n-1} c_n d_0 \\
c_n &= d_n - \sum_{k=1}^{n-1} \binom{n-1}{k-1} c_k d_{n-k}
\end{align}
$$
Donde el caso base es $c_0=c_1=1$. La complejidad para hallar $c_n$ es $O(n^2)$, veamos cómo mejorarla.

Sea $C(z)$ la egf de la sucesión $c_i$, y sea $D(z)$ la egf de la sucesión $d_i$. Es decir:
$$
\begin{align}
C(z) &= \sum_{n=0}^{\infty} \dfrac{c_n}{n!} z^n \\
D(z) &= \sum_{n=0}^{\infty} \dfrac{d_n}{n!} z^n
\end{align}
$$

De la primer fórmula, tenemos que:

$$
\begin{align}
d_n &= \sum_{k=1}^{n} \dfrac{(n-1)!}{(k-1)!(n-k)!} c_k d_{n-k} \\
\dfrac{d_n}{(n-1)!} &= \sum_{k=1}^{n} \dfrac{c_k}{(k-1)!} \cdot \dfrac{d_{n-k}}{(n-k)!} \\
\dfrac{n d_n}{n!} &= \sum_{k=1}^{n} \dfrac{k c_k}{k!} \cdot \dfrac{d_{n-k}}{(n-k)!} \\
\end{align}
$$

Hallemos la egf a ambos lados y dividamos entre $z$:
$$
\begin{align}
\sum_{n=1}^{\infty} \dfrac{n d_n}{n!} z^n &= \sum_{n=1}^{\infty} \left( \sum_{k=1}^{n} \dfrac{k c_k}{k!} \cdot \dfrac{d_{n-k}}{(n-k)!} \right) z^n \\
\sum_{n=1}^{\infty} \dfrac{n d_n}{n!} z^{n-1} &= \sum_{n=1}^{\infty} \left( \sum_{k=1}^{n} \dfrac{k c_k}{k!} \cdot \dfrac{d_{n-k}}{(n-k)!} \right) z^{n-1} \\
\end{align}
$$

Veamos a qué es igual la derivada de $C(z)$ y de $D(z)$:
$$
\begin{align}
C'(z) &= \sum_{n=1}^{\infty} \dfrac{n c_n}{n!} z^{n-1} \\
D'(z) &= \sum_{n=1}^{\infty} \dfrac{n d_n}{n!} z^{n-1}
\end{align}
$$

El lado izquierdo de la última ecuación es justamente $D'(z)$, y el derecho es una convolución de la sucesión $\dfrac{n c_n}{n!}$ y $\dfrac{d_n}{n!}$, es decir, $C'(z)D(z)$. Por lo tanto, $D'(z) = C'(z)D(z)$. Esta es una ecuación diferencial que se puede resolver por separación de variables:
$$
\begin{align}
C'(z) &= \dfrac{D'(z)}{D(z)} \\
\int C'(z) dz &= \int \dfrac{D'(z)}{D(z)} dz \\
C(z) &= \ln(D(z)) + c_0 \\
C(z) &= \ln(D(z)) + 1
\end{align}
$$

Finalmente, podemos hallar $D(z)$ con la fórmula en $O(n)$, y $C(z)$ en $O(n \log n)$.

:::

### Número de torneos fuertemente conexos

### [PolandBall and Many Other Balls](https://codeforces.com/contest/755/problem/G)
:::spoiler **Descripción**
Tenemos $n$ elementos ordenados del $1$ al $n$ y queremos formar $m$ grupos, donde cada uno consiste de uno o dos elementos adyacentes. Cada elemento puede pertenecer a lo más a un grupo. Sea $f(n,m)$ el número de formas de hacerlo, calcular $f(n,m)$ para toda $1 \leq m \leq k$.

Límites: $1 \leq n \leq 10^9$, $1 \leq k < 2^{15}$.
:::

:::spoiler **Ejemplo**
Para $n=3$ tenemos que:
- Si $m=1$ podemos dividir los elementos de las siguientes 5 maneras: $[1], [2], [3], [1,2], [1,2,3]$
- Si $m=2$ podemos dividir los elementos de las siguientes 5 maneras: $[1,2][3], [1][2,3], [1][2], [1][3], [2][3]$
- Si $m=3$ podemos dividir los elementos de la siguiente manera únicamente: $[1][2][3]$

Por lo tanto, $f(3,1)=5$, $f(3,2)=5$, $f(3,3)=1$.
:::

:::spoiler **Solución**
$f(n,m)$ se puede hallar con programación dinámica, ya que tenemos tres opciones:
- Tomemos el $n$-ésimo elemento y no hagamos nada con él. Hay $f(n-1,m)$ formas de hacerlo.
- Tomemos el $n$-ésimo elemento y lo metemos dentro de su propio grupo. Hay $f(n-1,m-1)$ formas de hacerlo.
- Tomemos el $n$-ésimo elemento y el $(n-1)$-ésimo elemento y los metemos en un grupo. Hay $f(n-2,m-1)$ formas de hacerlo.

Por lo tanto, $f(n,m) = f(n-1,m) + f(n-1,m-1) + f(n-2,m-1)$. Los casos base son:
$$
f(0,m) = \begin{cases}
1 &\mbox{si $m=0$} \\
0 &\mbox{si $m \geq 1$}
\end{cases} \\
f(1,m) = \begin{cases}
1 &\mbox{si $m \leq 1$} \\
0 &\mbox{si $m \geq 2$}
\end{cases}
$$

Si calculamos $f(n,m)$ de forma bruta, tendríamos una complejidad de $O(nk)$, lo cual no entra en tiempo.

Visualicemos $f(n,m)$ como una tabla, donde $n$ indica la fila y $m$ la columna:

$$
\begin{array}{|c|c|c|c|c|}
\hline
n / m & 0 & 1 & 2 & \ldots \\
\hline
0 & f(0,0) & f(0,1) & f(0,2) & \ldots \\
\hline
1 & f(1,0) & f(1,1) & f(1,2) & \ldots \\
\hline
2 &f(2,0) & f(2,1) & f(2,2) & \ldots \\
\hline
\end{array}
$$

Además, cada fila vamos a verla como un polinomio en $x$, es decir, por cada fila vamos a hallar su función generadora y la vamos a llamar $F_n(x)$:
$$
\begin{array}{|c|c|}
\hline
n & F_n(x) \\
\hline
0 & f(0,0) + f(0,1)x + f(0,2)x^2 + \ldots \\
\hline
1 & f(1,0) + f(1,1)x + f(1,2)x^2 + \ldots \\
\hline
2 & f(2,0) + f(2,1)x + f(2,2)x^2 + \ldots \\
\hline
\cdots & \cdots \\
\hline
\end{array}
$$

Por ejemplo, los casos base son ahora $F_0(x) = 1$ y $F_1(x)=1+x$. Ahora vamos a transformar la definición de $f(n,m)$ para hallar una recurrencia que involucre a $F_n(x)$ para $n \geq 2$:

$$
\begin{align}
F_n(x) &= \sum_{m=0}^{\infty} f(n,m) x^m \\
&= \sum_{m=0}^{\infty} [f(n-1,m) + f(n-1,m-1) + f(n-2,m-1)]x^m \\
&= \sum_{m=0}^{\infty} f(n-1, m)x^m + \sum_{m=0}^{\infty} f(n-1, m-1)x^m + \sum_{m=0}^{\infty} f(n-2, m-1)x^m \\
&= F_{n-1}(x) + \sum_{m=1}^{\infty} f(n-1, m-1)x^m + \sum_{m=1}^{\infty} f(n-2, m-1)x^m \\
&= F_{n-1}(x) + \sum_{m=0}^{\infty} f(n-1, m) x^{m+1} + \sum_{m=0}^{\infty} f(n-2, m)x^{m+1} \\
&= F_{n-1}(x) + x\sum_{m=0}^{\infty} f(n-1, m) x^m + x\sum_{m=0}^{\infty} f(n-2, m)x^m \\
&= F_{n-1}(x) + x F_{n-1}(x) + x F_{n-2}(x) \\
F_n(x) &= (1+x)F_{n-1}(x) + xF_{n-2}(x)
\end{align}
$$

Si hallamos de forma sucesiva las $F_n(x)$ usando la recurrencia anterior, tendríamos la misma complejidad de $O(nk)$.

Una forma de calcularla más rápido es usando exponenciación de matrices. Sea $A = \begin{pmatrix} 1+x & x \\ 1 & 0 \end{pmatrix}$ y sea $v_n = \begin{pmatrix} F_n(x) \\ F_{n-1}(x) \end{pmatrix}$, entonces tenemos que:
$$
Av_{n-1} = \begin{pmatrix} 1+x & x \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1}(x) \\ F_{n-2}(x) \end{pmatrix} = \begin{pmatrix} (1+x)F_{n-1}(x) + xF_{n-2}(x) \\ F_{n-1}(x) \end{pmatrix} = \begin{pmatrix} F_n(x) \\ F_{n-1}(x) \end{pmatrix} = v_n
$$

Por lo tanto, $v_2 = Av_1$, $v_3 = Av_2=A^2v_1$, $v_4=Av_3=A^3v_1$, y de forma general, $v_n=A^{n-1}v_1$. Podemos usar exponenciación de matrices para hallar $A^{n-1}$, pero recordemos que las entradas de $A$ son polinomios, por lo tanto hay que usar NTT para multiplicar sus entradas, logrando una complejidad de $O(k \log k \log n)$.

Vamos a intentar hallar $A^{n-1}$ con una complejidad que no dependa de $n$. Vamos a diagonalizar $A$ hallando su polinomio característico y sus raíces, que es $\det(A - zI) = \det \begin{pmatrix} 1+x - z & x \\ 1 & -z \end{pmatrix} = (1+x-z)(-z) - (x)(1) = z^2 - (1+x)z - x$, cuyas raíces son $z_{1,2} = \dfrac{1+x \pm \sqrt{(1+x)^2 + 4x}}{2}$.

Por lo tanto, si $A=PDP^{-1}$, entonces $D=\begin{pmatrix} z_1 & 0 \\ 0 & z_2 \end{pmatrix}$. Para hallar la matriz $P$ necesitamos hallar los vectores propios de $A$, es decir, por cada raíz del polinomio característico, vamos a hallar el espacio nulo de $A-zI$.

$$
\begin{align}
A-zI &= \begin{pmatrix} 1+x - z & x \\ 1 & -z \end{pmatrix} \\
&\to \begin{pmatrix} 1 & -z \\ 1+x - z & x \end{pmatrix} \\
&\to \begin{pmatrix} 1 & -z \\ 0 & x - (1+x-z)(-z) \end{pmatrix} \\
&= \begin{pmatrix} 1 & -z \\ 0 & x - z^2+(1+x)z \end{pmatrix} \\
&= \begin{pmatrix} 1 & -z \\ 0 & 0 \end{pmatrix}
\end{align}
$$

Para hallar los vectores propios $w_1 = \begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$ y $w_2 = \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$ correspondientes a $z_1$ y $z_2$, hacemos que $Aw_1 = z_1w_1$, lo que es equivalente a $(A-z_1I)w_1=0$, y de forma similar, $(A-z_2I)w_2=0$. Tenemos que:

$$
\begin{align}
(A-z_1I)w_1 &= 0 \\
\begin{pmatrix} 1 & -z_1 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} &= 0 \\
x_1 - z_1y_1 &= 0 \\
x_1 = z_1y_1
\end{align}
$$

De forma similar, $x_2 = z_2y_2$. Por lo tanto, $w_1 = \begin{pmatrix} z_1 \\ 1 \end{pmatrix}$ y $w_2 = \begin{pmatrix} z_2 \\ 1 \end{pmatrix}$. Entonces, $P = \begin{pmatrix} z_1 & z_2 \\ 1 & 1 \end{pmatrix}$. Tenemos que $P^{-1} = \dfrac{1}{z_1-z_2}\begin{pmatrix} 1 & -z_2 \\ -1 & z_1 \end{pmatrix}$.

Sabemos que $A=PDP^{-1}$, entonces $A^2=PDP^{-1}PDP^{-1}=PD^2P^{-1}$, de forma general, $A^{n-1} = PD^{n-1}P^{-1}$. Para hallar $D^{n-1}$ solo tenemos que elevar sus entradas en la diagonal a la $n-1$, o sea: $D^{n-1} = \begin{pmatrix} {z_1}^{n-1} & 0 \\ 0 & {z_2}^{n-1} \end{pmatrix}$. Pero recordemos que $z_{1,2} = \dfrac{1+x \pm \sqrt{1+6x+x^2}}{2}$, las cuales se pueden calcular usando la raíz cuadrada en serie de potencias. Para elevarlos a la $n-1$, usamos la exponencial.

Por lo tanto, la complejidad ahora queda $O(k \log k)$.
:::

### [Chef and Equations](https://www.codechef.com/problems/CHEFEQUA)

### [Series Sum](https://www.codechef.com/problems/SERSUM)
:::spoiler **Descripción**
Dados $n$ enteros $a_1, a_2, \ldots, a_n$, definimos a las funciones $f(x,k)$ y $g(t,k)$ como:

$$
\begin{align}
f(x,k) &= (x+a_1)^k + (x+a_2)^k + \cdots + (x+a_n)^k \\
g(t,k) &= f(0,k) + f(1,k) + \cdots + f(t,k)
\end{align}
$$

Dados $T$ y $K$ enteros, hallar $g(T,i)$ para $i=0,1,2,\ldots,K$ módulo $10^9+7$.

Límites:
- $1 \leq n \leq 10^5$
- $0 \leq a_i < 10^9+7$
- $1 \leq K \leq 5 \times 10^4$
- $1 \leq T \leq 10^{18}$

:::

:::spoiler **Ejemplo**
Sea $a=[1, 2]$, $K=3$ y $T=4$.

Tenemos que $f(x,k) = (x+1)^k + (x+2)^k$ y que:
$$
\begin{align}
g(4,i) &= f(0,i) + f(1,i) + f(2,i) + f(3,i) + f(4,i) \\
&= (1^i + 2^i) + (2^i + 3^i) + (3^i + 4^i) + (4^i + 5^i) + (5^i + 6^i) \\
&= 1 + 2 \times (2^i + 3^i + 4^i + 5^i) + 6^i
\end{align}
$$

Y la respuesta es:
$$
\begin{align}
g(4,0) &= 1 + 2 \times (1 + 1 + 1 + 1) + 1 = 10 \\
g(4,1) &= 1 + 2 \times (2 + 3 + 4 + 5) + 6 = 35 \\
g(4,2) &= 1 + 2 \times (4 + 9 + 16 + 25) + 36 = 145 \\
g(4,3) &= 1 + 2 \times (8 + 27 + 64 + 125) + 216 = 665
\end{align}
$$

:::

:::spoiler **Solución**
Tratemos de hallar una función generadora para la sucesión de valores $g(T,k)$, es decir, $\displaystyle G(z)=\sum_{k=0}^\infty g(T,k) z^k$. Tenemos que:
$$
\begin{align}
G(z) &= \sum_{k=0}^{\infty} \sum_{x=0}^{T} f(x, k) z^k \\
&= \sum_{k=0}^{\infty} \sum_{x=0}^{T} \sum_{i=1}^{n} (x+a_i)^k z^k \\
&= \sum_{x=0}^{T} \sum_{i=1}^{n} \sum_{k=0}^{\infty} (z(x+a_i))^k \\
&= \sum_{x=0}^{T} \sum_{i=1}^{n} \dfrac{1}{1-z(x+a_i)}
\end{align}
$$

Como ya no se puede simplificar más, intentemos ahora hallar $G(z)=\displaystyle \sum_{k=0}^\infty \dfrac{g(T,k)}{k!} z^k$, a la que le llamaremos la función generadora exponencial de la sucesión de valores. Tenemos que:
$$
\begin{align}
G(z) &= \sum_{k=0}^{\infty} \dfrac{1}{k!} \sum_{x=0}^{T} f(x, k) z^k \\
&= \sum_{k=0}^{\infty} \dfrac{1}{k!} \sum_{x=0}^{T} \sum_{i=1}^{n} (x+a_i)^k z^k \\
&= \sum_{x=0}^{T} \sum_{i=1}^{n} \sum_{k=0}^{\infty} \dfrac{(z(x+a_i))^k}{k!} \\
&= \sum_{x=0}^{T} \sum_{i=1}^{n} e^{z(x+a_i)} \\
&= \left( \sum_{x=0}^{T} e^{zx} \right) \left( \sum_{i=1}^{n} e^{za_i} \right) \\
&= \dfrac{1-(e^z)^{T+1}}{1-e^z} \sum_{i=1}^{n} \sum_{j=0}^{\infty} \dfrac{(z a_i)^j}{j!} \\
&= \dfrac{1-(e^z)^{T+1}}{1-e^z} \sum_{j=0}^{\infty} \left( \sum_{i=1}^{n} a_i^j \right) \dfrac{z^j}{j!} \\
\end{align}
$$

Sea $\displaystyle h_j = \sum_{i=1}^{n} a_i^j$, entonces $\displaystyle G(z) = \dfrac{1-(e^z)^{T+1}}{1-e^z} \sum_{j=0}^{\infty} h_j \dfrac{z^j}{j!}$. Intentemos hallar la función generadora ordinaria de la sucesión $h_j$, es decir, $\displaystyle H(z)=\sum_{j=0}^{\infty} h_j z^j$. Tenemos que:

$$
\begin{align}
H(z) &= \sum_{j=0}^{\infty} \sum_{i=1}^{n} a_i^j z^j \\
&= \sum_{i=1}^{n} \sum_{j=0}^\infty (a_i z)^j \\
&= \sum_{i=1}^{n} \dfrac{1}{1 - a_i z}
\end{align}
$$

Para hallar la suma anterior, podemos usar divide y vencerás para hallarla en una complejidad de $O(n \log^2 n)$. Podríamos tener un método $calc(l,r)$ que nos devuelva un par de polinomios, el numerador y el denominador de la suma de $l$ a $r$. El caso base es cuando $l=r$, ahí solo devolvemos $\{1, 1-a_lz\}$. Sea $m=\lfloor (l+r)/2 \rfloor$, para combinar las respuestas de $calc(l,m) = \{A, B\}$ y de $calc(m+1,r) = \{C, D\}$ en $calc(l,r)$, tenemos que $\dfrac{A}{B} + \dfrac{C}{D} = \dfrac{AD + BC}{BD}$, entonces devolvemos $\{AD+BC, BD\}$. La complejidad es $T(n) = 2T(n/2) + O(n \log n)$, es decir, $T(n) = O(n \log^2 n)$. Al final tendremos que $calc(1,n) = \{num, den\}$, y ahora sí hallamos $\dfrac{num}{den}$ con el inverso y una convolución.

Por lo tanto, ya que tenemos calculados los $K+1$ valores $h_j$, los sustituímos en $G(z)$:

$$
\begin{align}
G(z) &= \left( \dfrac{1-e^{z(T+1)}}{1-e^z} \right) \left( \sum_{j=0}^{\infty} h_j \dfrac{z^j}{j!} \right)
\end{align}
$$

Hallar dicho producto es fácil, pues solo requerimos de 2 convoluciones y 1 inverso. Al final no olvidemos multiplicar por $k!$ cada coeficiente de $G(z)$ para obtener la respuesta final.

:::

### [Chef and the Combination Lock](https://www.codechef.com/problems/CHEFSSM)

### [Power Sum](https://www.codechef.com/problems/PSUM)

### [Just Primes II](https://www.spoj.com/problems/JPM2/)

### [Chef and Rainbow Road](https://www.codechef.com/problems/RNBWROAD)

### [Chef and Same Old Recurrence 2](https://www.codechef.com/problems/JADUGAR2)

### [Perfect Permutations](https://www.hackerearth.com/problem/algorithm/perfect-permutations-september-clash/)