Góc nhìn: Khi viết ra hai hoán vị $1 \ \ 2 \ \ ... \ \ n-1 \ \ n$ và $p_1 \ \ p_2 \ \ ... \ \ p_{n-1} \ \ p_n$ thành hai hàng bằng nhau, mỗi khoảng cách giữa $i$ với $i+1$ $(0 \leq i \leq n)$ vẽ một đường kẻ. Tạo $n$ đường thẳng nối $i$ và $p_i$ ở hai hàng, tổng số giao điểm xuất hiện cũng chính bằng giá trị $\sum_{i=1}^{n} |i - p_i|$. Bởi với mỗi đường thẳng nối $i \rightarrow p_i$ sẽ đi qua chính xác $|i - p_i|$ điểm.
$\rightarrow$ Đưa về bài toán "đếm số hoán vị $p_1 ... p_n$ thỏa mãn tổng số giao điểm bằng $k$".


Giải quyết bài toán nêu trên bằng QHĐ. Ta đánh số các đường kẻ dọc từ $0$ đến $n$. Xét $i \leq n$ ta có thể tính được số cách nối từ điểm $u$ của hàng trên đến điểm $v$ của hàng dưới $(1 \leq u, v \leq i)$ sao cho tạo ra $k$ giao điểm, không giao với đường kẻ dọc $\leq i$.

Gọi $f[i][j][k]$ là số cách kẻ tạo ra $k$ giao điểm, còn $j$ điểm ở hàng trên chưa được nối, và các đường nối $u \rightarrow v$ không đi qua đường kẻ dọc thứ $i$. Vậy tại sao ta lại không lưu $u$ điểm chưa nối ở hàng trên và $v$ điểm như vậy ở hàng dưới? Bởi $u$ và $v$ sẽ cùng tăng giảm trong mọi trường hợp, nên $u$ sẽ luôn bằng $v$. Xét mỗi bộ $(i, j, x)$ ta có thể update $(i + 1, \ .., \ ..)$ theo $4$ trường hợp sau:
- Trường hợp $1$: Không nối thêm điểm nào
Số điểm chưa được nối sẽ tăng lên $1$, vì trước đó ta đã không nối $j$ điểm ở hàng trên, tính thêm điểm $i$. Bởi ta đang xét việc nối một điểm ở trước với điểm $i + 1$, rồi $i + 2$, ... nên dễ thấy trong $j + 1$ điểm chưa được nối ở hàng trên, đường nối của chúng với điểm $u$ bất kì hàng dưới chắc chắn sẽ đi qua đường kẻ dọc thứ $i$ $\rightarrow$ số giao điểm chắc chắn sẽ thêm $2 * (j + 1)$.
$\rightarrow f[i + 1][j + 1][x + 2*(j+1)] += f[i][j][x]$
- Trường hợp $2$: Nối điểm $i + 1$ ở hàng trên với $i + 1$ ở hàng dưới.
Số điểm chưa được nối sẽ giữ nguyên, vì khi xét thêm điểm $i + 1$ ta sẽ có $j + 1$ điểm ở hàng trên, nhưng vì ta sẽ nối $i + 1$ hàng trên với $i + 1$ hàng dưới nên số điểm chưa được xét sẽ là $j + 1 - 1$. Tương tự như trên, số giao điểm chắc chắn sẽ tăng thêm $2 * j$.
$\rightarrow f[i + 1][j][x + 2 * j] += f[i][j][x]$
- Trường hợp $3 \ (j > 0)$: Nối điểm $i + 1$ ở hàng trên với $v \leq i$ bất kì ở hàng dưới hoặc ngược lại.
Tương tự trường hợp $2$, số điểm chưa nối sẽ giữ nguyên là $j$, và số giao điểm chắc chắn sẽ tăng thêm $2 * j$. Có $j$ cách chọn các điểm ở hàng dưới để nổi với $i + 1$ ở hàng trên, và cũng có $j$ cách chọn các điểm ở hàng trên để nối với điểm $i + 1$ ở hàng dưới. Vì vậy số cách chọn sẽ là $f[i][j][x] * 2 * j$.
$\rightarrow f[i + 1][j][x + 2 * j] += f[i][j][x] * j * 2$
- Trường hợp $4 \ (j > 0)$: Nối đồng thời điểm $i + 1$ ở hàng trên với $u \leq i$ ở hàng dưới và điểm $v \leq i$ ở hàng dưới với $i + 1$ ở hàng trên.
Ta thấy có hai điểm $u$ và $v$ được chọn ở hàng trên, tương tự ở hàng dưới, vì vậy số điểm chưa được nối sẽ giảm đi $1$. Nói cách khác $j' = j + 1 - 2 = j - 1$. Về số cách chọn $u, v$ thỏa mãn, dễ thấy có $j$ cách chọn $u$ ở hàng trên và $j$ cách chọn $v$ ở hàng dưới, do đó có tổng tộng $f[i][j][x] * j^2$ cách chọn thỏa mãn.
$\rightarrow f[i + 1][j - 1][x + 2 * (j - 1)] += f[i][j][x] * j^2$

Độ phức tạp: $O(n^2*k)$