CSES - Permutations II

Solution 1 - Connected Components DP

Define $f_{i,j,k}$ as the number of valid configurations of the numbers from $1$ to $i$ into $j$ "connected components", where value $i$ has $k$ borders. For instance, the set of intervals $\{[1,6],[2,3,5],[7],[4,8,9]\}$ would be counted in the state $f_{9,4,1}$.

1. If $i$ has no borders, then $i$ must point two existing connected compontents.
2. If $i$ has one border, then $i$ must be appended on to an existing connected component.
3. If $i$ has two borders, it must be inserted as its own connected component.

This corresponds to the following transitions:

The base case is $f_{0,0,0}=1$, and the final answer is $\sum_k f_{n,1,k}$.

Implementation

Time Complexity: $\mathcal{O}(n^2)$

Copy
#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);

Solution 2 - OEIS

Brute forcing the first few terms and plugging the sequence into OEIS yields OEIS - A002464, which is exactly what we are looking for. This gives us the simpler recurrence $a_i=(i+1)a_{i-1} - (i-2)a_{i-2} - (i-5)a_{i-3} + (i-3)a_{i-4}$.

Implementation

Time Complexity: $\mathcal{O}(n)$

Copy
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])