Skip to Content
CTRL K

Permutations II

Solución 1 - DP de componentes conexas

Definimos fi,j,kf_{i,j,k} como el número de configuraciones válidas de los números de 11 a ii en jj “componentes conexas”, donde el valor ii tiene kk bordes. Por ejemplo, el conjunto de intervalos {[1,6],[2,3,5],[7],[4,8,9]}\{[1,6],[2,3,5],[7],[4,8,9]\} se contaría en el estado f9,4,1f_{9,4,1}.

  1. Si ii no tiene bordes, entonces ii debe unir dos componentes conexas existentes.
  2. Si ii tiene un borde, entonces ii debe añadirse a una componente conexa existente.
  3. Si ii tiene dos bordes, debe insertarse como su propia componente conexa.

Esto corresponde a las siguientes transiciones:

fi,j,0=j(j+1)fi−1,j+1,0+j2fi−1,j+1,1+j(j−1)fi−1,j+1,2fi,j,1=2jfi−1,j,0+(2j−1)fi−1,j,1+(2j−2)fi−1,j,2fi,j,2=fi−1,j−1,0+fi−1,j−1,1+fi−1,j−1,2 \begin{align*} f_{i,j,0}&=j(j+1)f_{i-1,j+1,0}+j^2f_{i-1,j+1,1}+j(j-1)f_{i-1,j+1,2}\\ f_{i,j,1}&=2jf_{i-1,j,0}+(2j-1)f_{i-1,j,1}+(2j-2)f_{i-1,j,2}\\ f_{i,j,2}&=f_{i-1,j-1,0}+f_{i-1,j-1,1}+f_{i-1,j-1,2}\\ \end{align*}

El caso base es f0,0,0=1f_{0,0,0}=1, y la respuesta final es ∑kfn,1,k\sum_k f_{n,1,k}.

Implementación

Complejidad temporal: O(n2)\mathcal{O}(n^2)

#include <bits/stdc++.h>
 
const int MOD = 1000000007;
 
int main() {
	int N;
	std::cin >> N;
	std::vector dp(N + 1, std::vector<std::array<long long, 3>>(N + 2));
	for (auto &a : dp)
		for (auto &b : a) b.fill(0);
	dp[0][0][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j][0] =
			    (j * (j + 1) * dp[i - 1][j + 1][0] + j * j * dp[i - 1][j + 1][1] +
			     j * (j - 1) * dp[i - 1][j + 1][2]) %
			    MOD;
			dp[i][j][1] = (2 * j * dp[i - 1][j][0] + (2 * j - 1) * dp[i - 1][j][1] +
			               (2 * j - 2) * dp[i - 1][j][2]) %
			              MOD;
			dp[i][j][2] =
			    (dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]) % MOD;
		}
	}
	std::cout << (dp[N][1][0] + dp[N][1][1] + dp[N][1][2]) % MOD << '\n';
}

Solución 2 - OEIS

Haciendo fuerza bruta de los primeros términos y metiendo la secuencia en OEIS se obtiene OEIS - A002464 , que es exactamente lo que buscamos. Esto nos da la recurrencia más simple ai=(i+1)ai−1−(i−2)ai−2−(i−5)ai−3+(i−3)ai−4a_i=(i+1)a_{i-1} - (i-2)a_{i-2} - (i-5)a_{i-3} + (i-3)a_{i-4}.

Implementación

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

N = int(input())
dp = [0] * (N + 1)
dp[0], dp[1] = 1, 1
for i in range(4, N + 1):
	dp[i] = (
		(i + 1) * dp[i - 1]
		- (i - 2) * dp[i - 2]
		- (i - 5) * dp[i - 3]
		+ (i - 3) * dp[i - 4]
	) % 1000000007
print(dp[N])
Fundamentos