Moo Route

Intentemos visualizar los caminos así:

Consideremos construir una solución de forma recursiva. Si construimos un camino que satisface las restricciones $A_{i + 1}...A_n$, ¿cómo obtenemos un camino que satisface $A_i...A_n$?

Consideremos construir una solución de forma recursiva. Si construimos un camino que satisface las restricciones $A_{i + 1}...A_n$, ¿cómo obtenemos un camino que satisface $A_i...A_n$? Y si conocemos $C_{i + 1}$, el número de caminos que satisfacen $A_{i + 1}...A_n$, ¿cómo obtenemos $C_i$?

Caso 1: $A_i \leq A_{i + 1}$

Digamos que $A = [4, 6, 2]$. Si tomamos un camino que satisface $A_1...A_2$ (rojo), ¿cómo lo extendemos a un camino que satisface $A_0...A_2$?

Los movimientos en azul son obligatorios: nuestro camino debe empezar en 0 y terminar en 0. Sin embargo, necesitamos elegir dos movimientos grises más para satisfacer $A_0 = 4$. Si elegimos el movimiento 1, también debemos elegir el movimiento 2; de lo contrario, nuestro camino no conectará. De forma similar, si elegimos 3, también debemos elegir 4. ¡Nótese que elegir los caminos grises no aumenta el número de giros!

Para generalizar, asumiendo que nuestro camino construido para $A_{i + 1}...A_n$ minimiza los giros, esto también significa que cualquier camino que construyamos de la forma de arriba para $A_i...A_n$ minimizará los giros también. Para la relación de $C_i$ con $C_{i + 1}$, nótese que en el ejemplo de arriba, tenemos 2 “unidades” (movimientos 1, 2 y movimientos 3, 4) de las cuales necesitamos elegir 1: ya tenemos 1 unidad, las dos azules, y necesitamos $B_i = \frac{A_i}{2}$ unidades en total. Así, en general, tendremos que elegir $B_i - 1$ unidades de $B_{i + 1} - 1$ unidades, lo que nos da que $\boxed{C_i = {B_{i + 1} - 1 \choose B_i - 1} * C_{i + 1}}$.

Caso 2: $A_i > A_{i + 1}$

Digamos que $A$ es ahora $[6, 4, 6]$. Tomemos un camino válido para $A_1...A_2$ (rojo) y transformémoslo en uno para $A_0...A_2$:

Hay una razón por la que lo dibujé así, pero así es como se vería normalmente:

Sin embargo, volviendo al primer diagrama, ¿de cuántas formas se pueden dibujar los enlaces grises? Bueno, necesitamos enlazar las 2 unidades rojas con las 3 unidades azules, y el orden de las unidades rojas está fijo (no podemos enlazar la unidad roja 2 con la unidad azul 1 y la unidad roja 1 con la unidad azul 2, por ejemplo); por lo tanto, el número de formas de dibujar enlaces grises es simplemente $3 \choose 2$ en este caso.

Nótese que esta construcción también minimiza los giros, ya que “reutilizamos” tantos giros como sea posible (p. ej. la unidad azul 1 y la unidad roja 1 enlazadas juntas tienen la misma cantidad de giros que la unidad roja 1 sola). Así, cuando $A_i > A_{i + 1}$, $\boxed{C_i = {B_i \choose B_{i + 1}} * C_{i + 1}}$.

Implementación

Complejidad temporal: $\mathcal{O}(N + A\log{M})$

#include <iostream>
using namespace std;
using ll = long long;
 
const int A = 1e6 + 1;
const int M = 1e9 + 7;
const int N = 1e5;
ll fact[A], inv_fact[A], a[N];
 
// binary exponentiation:
// https://usaco.guide/gold/modular#modular-exponentiation
ll exp(ll x, ll n) {
	x %= M;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % M; }
		x = x * x % M;
		n /= 2;
	}
	return res;
}
 
// https://usaco.guide/gold/combo#method-2-factorial-definition-modular-inverses---mathcalon--log-mod
ll C(ll n, ll k) { return fact[n] * inv_fact[n - k] % M * inv_fact[k] % M; }
 
int main() {
	// precomputamos factoriales e inversos
	fact[0] = inv_fact[0] = 1;
	// fact[i] = i!, inv_fact[i] = inverso de i!
	for (int i = 1; i < A; i++) {
		fact[i] = fact[i - 1] * i % M;
		// inverso de x mód M = x^(M - 2) cuando M es primo
		inv_fact[i] = exp(fact[i], M - 2);
	}
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		// convertimos a[i] a b[i]
		a[i] /= 2;
	}
 
	ll ans = 1;  // caso base: C_{n - 1} = 1
	for (int i = n - 2; i >= 0; i--) {
		// calculamos C_i
		if (a[i] > a[i + 1]) {
			ans = ans * C(a[i], a[i + 1]) % M;
		} else {
			ans = ans * C(a[i + 1] - 1, a[i] - 1) % M;
		}
	}
 
	cout << ans << endl;
}