Almost Identity Permutations

Análisis oficial 

Explicación

Podemos iterar de $0$ a $k$ y barajar exactamente $k$ posiciones de la permutación. Después de barajar, exactamente $k$ posiciones de la permutación deberían ser distintas mientras las posiciones restantes permanecen iguales para cumplir el criterio de casi identidad.

Consideremos cómo contar las formas de barajar exactamente $m$ posiciones de la permutación. Primero hay que elegir exactamente $m$ posiciones en las permutaciones de entre $n$ índices, que es ${n \choose m}$. Ahora consideremos cómo barajar las $m$ posiciones. Podemos considerar permutaciones. Sin embargo, en algunas permutaciones, no todas las posiciones están completamente barajadas.

Por ejemplo, si $n = 4$.

La permutación identidad será $1$ $2$ $3$ $4$.

Digamos que queremos reordenar los primeros 3 elementos.

Una permutación posible es: $1$ $3$ $2$ $4$.

En esta permutación, el primer elemento sigue en el mismo lugar, que no es el resultado deseado (no barajamos todos los elementos que queremos reordenar).

Así, necesitamos hallar todas las permutaciones donde todos los elementos están fuera de lugar. Sin embargo, como $k$ es relativamente pequeño, podemos hacer fuerza bruta sobre las permutaciones para hallar el número de permutaciones válidas.

Podemos sumar el número de permutaciones válidas multiplicado por el número de formas de elegir una permutación de esa longitud.

Implementación

Complejidad temporal: $\mathcal{O}(NK)$

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main() {
	int n, k;
	cin >> n >> k;
 
	// Use Pascal's Identity to precalculate combinations.
	ll c[n + 1][k + 1];
	fill_n(&c[0][0], (n + 1) * (k + 1), 0);
	for (int i = 0; i <= n; i++) { c[i][0] = 1; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) { c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; }
	}
 
	ll ans = 0;
	// Iterate over number of positions to shuffle.
	for (int i = 0; i <= k; i++) {
 
		// Calculate number of valid permutations result in all positions
		// shuffled.
		int a[i];
		for (int j = 0; j < i; j++) a[j] = j;
		int amt = 0;
		do {
			bool valid = 1;
			for (int j = 0; j < i; j++)
				if (a[j] == j) valid = 0;
			if (valid) amt++;
		} while (next_permutation(a, a + i));
 
		// Add the number of valid permutations of i elements multiplied by the
		// number of ways to choose i elements.
		ans += c[n][i] * amt;
	}
 
	cout << ans << endl;
}