Balanced Subsequences

Explicación

Primero, busquemos una forma sencilla de hallar la subsecuencia balanceada más larga (LBS, longest balanced subsequence) de un string $s$ dado. Para ello, podemos usar un algoritmo voraz simple: recorremos $s$ de izquierda a derecha y, cuando encontramos un ), lo emparejamos con algún ( aún no emparejado visto hasta el momento. Aquí hay una visualización de este algoritmo, donde las líneas negras muestran los pares formados y los trazos azules hacia abajo representan los ) no emparejados:

Observemos que un trazo azul hacia abajo queda sin emparejar sii es el primer trazo hacia abajo que va de $y = i$ a $y = i - 1$ para algún $i \le 0$. Por lo tanto, el número total de trazos hacia abajo no emparejados es precisamente el mínimo $y$ que alcanza nuestro camino. Si queremos una LBS de longitud $2k$ debemos tener $k$ trazos hacia abajo emparejados y $m - k$ trazos hacia abajo no emparejados, así que la pregunta pasa a ser:

¿Cuántos caminos con $n$ trazos hacia arriba y $m$ trazos hacia abajo tocan, pero no cruzan, la recta $y = k - m$?

Por conveniencia, podemos eliminar la condición de “no cruzar” contando el número de caminos que bajan de $y = k - m$ (inclusive) y restando el número de caminos que bajan de $y = k - m - 1$. Esto equivale a contar el número de strings con longitud de LBS a lo sumo $k$ y restar los que tienen longitud de LBS a lo sumo $k - 1$.

Para contar el número de caminos que bajan de $y = k - m$, consideramos tres casos:

• $m \le k$. En este caso, siempre empezamos por debajo de la recta en $y = 0 \le k - m$, así que todos los $\binom{n + m}{m}$ caminos son válidos.
• $n \le k$. En este caso, siempre terminamos por debajo de la recta en $y = n - m \le k - m$, así que todos los $\binom{n + m}{m}$ caminos son válidos.
• $m \gt k, n \gt k$. En este caso, como empezamos por encima de la recta y terminamos por encima de la recta, podemos aplicar la biyección por reflexión indicada en el módulo principal para darnos cuenta de que en cambio podemos contar el número de caminos que terminan en $y = 2(k - m) - (n - m)$ = $2k - m - n$. Podemos verificar que, tras esta reflexión, nuestro nuevo camino tendrá $k$ trazos hacia arriba y $n + m - k$ trazos hacia abajo, lo que genera un total de $\binom{n + m}{k}$ caminos.

Para terminar, solo hay que evaluar esta expresión para $k$ y $k - 1$ y restar los dos valores.

Implementación

Complejidad temporal: $\mathcal{O}(\max(n, m, k)^2)$

Calcular los coeficientes binomiales se puede hacer más rápido preprocesando factoriales, pero no hace falta para este problema.

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
 
const int MX = 5000;
const int M = 1e9 + 7;
void ad(int &a, int b) {
	if ((a += b) >= M) a -= M;
};
int sb(int a, int b) { return ((a -= b) < 0 ? a + M : a); };
int binom[MX][MX];
 
// número de strings con LBS <= k
// es decir, que tocan la recta y = k - m
int f(int n, int m, int k) {
	if (n > m) swap(n, m);
	if (n <= k) return binom[n][m];
	else return binom[k][n + m - k];
}
 
void ac() {
	int n, m, k;
	cin >> n >> m >> k;
	cout << sb(f(n, m, k), f(n, m, k - 1)) << "\n";
}
 
int32_t main() {
	// calcular coeficientes binomiales: binom[x][y] = C(x + y, y)
	binom[0][0] = 1;
	for (int i = 0; i + 1 < MX; i++) {
		for (int j = 0; j + 1 < MX; j++) {
			ad(binom[i + 1][j], binom[i][j]);
			ad(binom[i][j + 1], binom[i][j]);
		}
	}
	int t;
	cin >> t;
	while (t--) ac();
}