Skip to Content
CTRL K

Med and Mex

Análisis oficial (C++) 

Explicación

Primero, deberíamos intentar entender cómo se ve en general una secuencia buena. Como se menciona en el problema, una secuencia buena debe tener su mediana igual a su mex. Con esa definición, podemos hacer las siguientes observaciones.

  1. Nuestros subarreglos deben ser de longitud par
  2. Los dos valores de la mediana de nuestro subarreglo deben estar a una distancia par

Con eso de lado, podemos hacer algunas observaciones más. La primera es que los elementos 1,2,3⋯len21, 2, 3 \cdots \frac{\text{len}}{2} deben estar presentes en nuestro subarreglo. Si no fuera así, nuestro mex sería menor que len2\frac{\text{len}}{2}, lo que significa que no puede ser igual a la mediana de nuestro subarreglo.

Nuestra siguiente observación es una mejora de la segunda. La distancia entre nuestros dos valores de la mediana debe ser igual a 22. Si no fuera así, nuestro mex sería menor que nuestra mediana.

Con esas observaciones, podemos calcular la respuesta con un poco de combinatoria. La forma más fácil es iterar sobre la longitud del subarreglo y contar el número de subarreglos buenos. Luego, podemos contar el número de formas de rellenar los elementos alrededor de nuestros subarreglos. Esto funciona porque cada longitud de subarreglo se corresponde con un único valor de mediana/mex, lo que nos permite calcular nuestras respuestas finales.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
 
using ll = long long;
 
constexpr int MOD = 998244353;
 
// BeginCodeSnip{Modular Exponentiation (from the module)}
ll exp(ll x, ll n, ll m) {
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
 
	return res;
}
// EndCodeSnip
 
namespace Combo {
std::vector<ll> fact;
std::vector<ll> inv;
 
void init(int n) {
	fact.resize(n + 1);
	inv.resize(n + 1);
	fact[0] = 1;
	for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; }
 
	inv[n] = exp(fact[n], MOD - 2, MOD);
	for (int i = n; i >= 1; i--) { inv[i - 1] = (inv[i] * i) % MOD; }
}
 
ll nck(int n, int k) {
	if (k > n || k < 0) { return 0ll; }
	return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
}  // namespace Combo
 
int main() {
	Combo::init(1e5);
 
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		std::cin >> n;
 
		std::vector<int> res(n + 1);
		for (int len = 2; len <= n; len += 2) {
			/**
			 * Un subarreglo válido debe contener todos los elementos de 1...len/2, y
			 * además tener 2 + len/2. El resto de los valores solo necesita ser mayor
			 * que 2 + len/2.
			 *
			 * Para contar todas las formas, primero determinamos todos los subarreglos
			 * válidos, y luego calculamos el número de permutaciones válidas para cada
			 * subarreglo.
			 */
			const int mex = 1 + len / 2;
			int subs =
			    1ll * Combo::nck(n - mex - 1, len / 2 - 1) * Combo::fact[len] % MOD;
			int rest = 1ll * Combo::fact[n - len] * (n - len + 1) % MOD;
			res[mex] = 1ll * subs * rest % MOD;
		}
 
		for (int i = 1; i <= n; i++) { std::cout << res[i] << " \n"[i == n]; }
	}
}
Fundamentos