Cho mảng A = [1..n]. Tìm số hoán vị S1 sau đúng k lần đổi chỗ liền kề (swap i và i+1). Và số hoán vị S2 sau tối đa k lần đổi chỗ bất kỳ (không nhất thiết liền kề).
Ví dụ: n=3, k=2 → S1=3, S2=6.
Giải thuật
- S1: số hoán vị có số đảo (inversion) bằng k modulo 2? Thực tế dùng DP: A[x] = số hoán vị n phần tử có đúng x đảo liền kề? Mã dùng truy hồi phức tạp.
- S2: số hoán vị có số đảo (inversion) ≤ k. Dùng số Stirling loại 1? Mã tính C[x] = số hoán vị n phần tử có x vòng? Không rõ.
- Mã mẫu sử dụng DP với mảng A và C, modulo 10^9+7.
Ví dụ mã Python
p = 10**9 + 7
def solve(n, k):
A = [1]
C = [1]
for n_val in range(2, n + 1):
B = A
A = [1]
D = C
C = [1]
for x in range(1, min(k + 1, n_val * (n_val - 1) // 2 + 1)):
A.append((A[-1] + (B[x] if x < len(B) else 0) - (B[x - n_val] if 0 <= x - n_val else 0)) % p)
for x in range(1, n_val - 1):
C.append((D[x] + (n_val - 1) * D[x - 1]) % p)
C.append(n_val * D[-1] % p)
return sum(A[k % 2 : k + 1 : 2]) % p, C[min(n - 1, k)]
n = 3
k = 2
print(solve(n, k)) # Output: (3, 6)
Đầu vào
3, 2
Đầu ra
3, 6