\documentclass[a4paper,article,10pt]{article}
\usepackage{geometry}
\ttfamily
\usepackage[dvips]{graphicx,psfrag,overpic,color}
\usepackage{latexsym} 
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{pstricks}
\usepackage[postscript]{ucs}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{fancyhdr}
\usepackage{listings}
\geometry{margin=1.5cm}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\rhead{\thepage}
\chead{Espirales - ghastlyX}
\rfoot{\thepage}

\newtheorem{teo}{{Teorema}}
\newtheorem{recu}{{Recurrencia}}
\newtheorem*{lema}{{Lema}}
\newtheorem*{coro}{{Corolario}}
\newenvironment{demo}[1][Demostración:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{defi}[1][Definición]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{exemple}[1][Ejemplo]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remarca]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}
\noindent Se va a proceder paso a paso en la resoluci\'on de este problema. 
Dejando a un lado la soluci\'on por backtracking, puesto que es demasiado 
ineficiente, se puede considerar una primera soluci\'on usando programaci\'on din\'amica. 
Basta hacer un par de consideraciones para llegar a esta primera 
soluci\'on. Sea $f(n, m)$ el n\'umero de espirales diferentes (sin tomar m\'odulo) en un tablero de $n\times m$.
\begin{lema}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(m, n)$.
\end{lema}
\begin{demo}
Es evidente por simetr\'ia. $\blacksquare$
\end{demo}

\noindent Visto esto, dado un tablero de $n\times m$, las posibles espirales 
son las que realizan una \textbf{L} y se acaban y las que despu\'es de realizarla 
siguen avanzando. Esta \textbf{L} primero puede avanzar $n$ casillas y despu\'es 
puede bajar hasta $m$ casillas, dando un total de $nm$ posibles \textbf{L}s. 
Teniendo en cuenta que tras realizar la \textbf{L} vuelve a quedar un tablero de 
$i\times j$, donde $i + 1 \leq n$ y $j + 1 \leq m$ son las dimensiones de 
dicha \textbf{L}, se obtiene una primera recurrencia:

\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que 
$f(n, m) = nm + \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}f(i, j)$.
\end{recu}
\noindent Con esta recurrencia se obtiene un primer c\'odigo, cuya complejidad es $O(n^2m^2)$:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001]; //Tabla para la dinamica

long long f(int n, int m) {
    if (M[n][m] == -1) { //Si no esta calculado
        //Si el simetrico esta calculado, se devuelve ese por el lema
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n*m% MOD; //Espirales en forma de L sin continuar
        //Se suma el resto de espirales
        for (int i = 1; i <= n - 1; ++i) 
            for (int j = 1; j <= m - 1; ++j)
                M[n][m] = (M[n][m] + f(i,j))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    //Inicializacion de la tabla a -1
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Esta recurrencia puede simplificarse, para as\'i eliminar uno de los 
dos bucles de cada estado en la din\'amica. Si en lugar de considerar la 
\textbf{L}, se avanza tan solo en la primera direcci\'on, se tienen $n$ posibles 
espirales m\'as las que luego siguen creciendo en el tablero que queda, de 
dimensiones $i\times (m - 1)$, donde $1 \leq i \leq n$ es lo que se avanza antes 
de seguir. Con esto se obtiene la segunda recurrencia:
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que 
$f(n, m) = n + \sum\limits_{i = 1}^{n}f(i, m - 1)$.
\end{recu}
\noindent Esta segunda recurrencia permite conseguir una complejidad de $O(n^2m)$. 
El siguiente c\'odigo muestra como usarla adaptando el primer c\'odigo:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001];

long long f(int n, int m) {
    if (M[n][m] == -1) {
        if (m == 1) return M[n][m] = n;
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n% MOD; //Posibles inicios de la L
        //Suma del resto de espirales
        for (int i = 1; i <= n; ++i) 
            M[n][m] = (M[n][m] + f(i, m - 1))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Si bien este c\'odigo es bastante m\'as r\'apido que el primero, 
se puede mejorar a\'un m\'as trabajando un poco m\'as la recurrencia. El siguiente 
resultado muestra como poder hacerlo.
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$.
\end{recu}
\begin{demo}
Queremos ver que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$. 
Aplicando la segunda recurrencia, se tiene que ser\'a cierto si y s\'olo si $n + \sum\limits_{i = 
1}^{n}f(i, m - 1) = n - 1 + \sum\limits_{i = 1}^{n - 1}f(i, m - 1) + n + \sum\limits_{i = 1}^{n}f(i, m - 2 ) + 1$ 
es cierto. Simplificando esta segunda 
expresi\'on queda $f(n, m - 1) = n + \sum\limits_{i = 1}^{n}f(i, m - 2)$, 
que es cierta, puesto que es precisamente la segunda recurrencia vista 
anteriormente. $\blacksquare$
\end{demo}
\noindent Por esta recurrencia y el lema se obtiene el \'ultimo resultado:
\begin{coro}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = \binom{n+m}{m} - 1$.
\end{coro}
\noindent Por \'ultimo, el c\'odigo que utiliza este resultado:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
using namespace std;

int M[2002][2002];
const int MOD = 1000000000;

int main() {
    int n, m;
    for (int i = 0; i < 2002; ++i) M[i][0] = M[i][i] = 1;
    for (int i = 2; i < 2002; ++i) 
        for (int j = 1; j < i; ++j)  
            M[i][j] = (M[i - 1][j - 1] + M[i - 1][j])%MOD;
    cin >> n >> m;
    cout << (M[n + m][m] + MOD - 1)%MOD << endl;
}
\end{lstlisting}
A continuaci\'on se puede ver una comparativa de los diferentes c\'odigos con diferentes entradas:\\\\
\begin{tabular}{|c|c|c|c|c|}
\hline
& $n=m=100$ & $n=m=500$ & $n=m=750$& $n=m=1000$ \\
\hline
C\'odigo 1 & 0m0.288s & 2m31.501s & 12m44.252s & No realizado\\
\hline
C\'odigo 2 & 0m0.012s & 0m0.492s & 0m1.688s & 0m4.280s \\
\hline
C\'odigo 3 & 0m0.032s & 0m0.032s & 0m0.032s & 0m0.032s\\
\hline
\end{tabular}
\end{document}