SKYLINE

Explicación

El skyline consiste en N rascacielos con alturas distintas de 1 a N, dispuestos de izquierda a derecha. El director quiere evitar cualesquiera tres edificios en posiciones i < j < k tales que: height[i] < height[j] < height[k]. Llamemos a esto un patrón 123.

Idea de la solución

Esta pregunta se reduce esencialmente a hallar el n-ésimo número de Catalan.

Como hecho general, el número de permutaciones de longitud n que evitan cualquier patrón de longitud 3 (como 123, 132, 213) es igual a $C_n$ . Demostración

En este código se usa un enfoque de DP (en lugar de la fórmula) porque la pregunta pide el valor módulo 1000000. Como este no es un número primo, no se puede usar el pequeño teorema de Fermat para hallar factoriales inversos.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$ de preprocesamiento, $\mathcal{O}(1)$ por consulta

C++


 
#include <bits/stdc++.h>
using namespace std;
 
static const int MAXN = 1000;
static const int MOD = 1000000;
 
int x;
vector<int> C(MAXN + 1);
 
// BeginCodeSnip{Catalan Numbers Preprocessing}
void compute_catalan() {
	C[0] = C[1] = 1;
	for (int i = 2; i <= MAXN; ++i) {
		C[i] = 0;
		for (int j = 0; j < i; ++j) { C[i] = (C[i] + 1LL * C[j] * C[i - j - 1]) % MOD; }
	}
}
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	compute_catalan();
 
	while (cin >> x && x != 0) { cout << C[x] << '\n'; }
 
	return 0;
}