Hoán vị K-nghịch thế

Cần biết trước

Nguyên lí bao hàm loại trừ
Bài toán Chia kẹo Euler

Đề bài

Tham khảo

Tóm tắt

Cho hai số nguyên $n, k$. Đếm số lượng hoán vị của dãy ${1, 2, \dots, n}$ có $k$ cặp nghịch thế.

Subtask 1: $1 \leq n \leq 3000, 0 \leq k \leq \min(C^2_n, 3000)$
Subtask 2: $1 \leq n \leq 10^5, 0 \leq k \leq \min(C^2_n, 10^5)$

Phân tích

Subtask 1: Quy hoạch động

Độ phức tạp: $\mathcal{O}(nk)$

Trước khi đến với lời giải chính của bài này. Ta xét một hướng tiếp cận quy hoạch động khi $n$ và $k$ nhỏ. Gọi $\text{dp}[i][j]$ là số lượng hoán vị của dãy ${1, 2, \dots, i}$ có $j$ nghịch thế, ta dễ có công thức sau: $$ \text{dp}[i][j] = \sum_{x = 0}^{i-1} \text{dp}[i-1][j-x] $$

Giải thích công thức

Ở một trạng thái $(i, j)$ của hàm quy hoạch động, ta có thể đặt phần tử $i$ vào một trong $i$ vị trí của hoán vị ${1, 2, \dots, i-1}$ đã dựng trước đó. Số nghịch thế thay đổi như sau:

Đặt vào vị trí cuối dãy, số nghịch thế không thay đổi.
Đặt vào trước phần tử cuối, số nghịch thế tăng lên $1$ do phần tử $i$ lớn hơn các phần tử đã điền và có 1 phần tử đứng sau $i$.
…
Đặt vào vị trí đầu dãy, số nghịch thế tăng lên $i-1$ do có $i-1$ phần tử nhỏ hơn $i$ và đứng sau $i$.

Tóm lại, khi đặt phần tử $i$ vào một vị trí trong hoán vị đã dựng, số nghịch thế tăng lên sẽ bằng số phần tử đứng sau $i$, do $i$ lớn hơn tất cả phần tử đã điền.

Đáp án của bài toán sẽ là $\text{dp}[n][k]$. Ta sẽ được thuật toán có độ phức tạp là $\mathcal{O}(nk^2)$, từ đó ta có thể dùng mảng cộng dồn để cải tiến thành $\mathcal{O}(nk)$.

Subtask 2: Bao hàm loại trừ

Độ phức tạp: $\mathcal{O}(k\sqrt{k})$

Nhận xét

Trong công thức quy hoạch động trên, ta nhận thấy khi thêm phần tử thứ $i$ vào hoán vị, số cặp nghịch thế lại tăng thêm. Ta gọi lượng tăng thêm đó là $x_i$. Khi đó, bài toán trở thành đếm số dãy số $(x_1, x_2, \dots, x_n)$ phân biệt thỏa mãn: $$ x_1 + x_2 + \dots + x_n = k \text { và } 0 \leq x_i \leq i-1 $$

Xét phiên bản đơn giản hơn của bài toán: tìm số lượng nghiệm nhưng không có cận trên của $x_i$. Ta dễ dàng dùng công thức Chia kẹo Euler và tìm được đáp án của bài toán là $C_{n-1+k}^{n-1}$. Như vậy, ta cần phải tìm cách loại bỏ điều kiện $x_i \leq i-1$ để có thể dùng công thức trên.

Lời giải

Gọi $f(j)$ là số nghiệm của bài toán sao cho có ít nhất $j$ phần tử $x_i \geq i$ (phần tử xấu). Giả sử, ta xác định được $j$ phần tử xấu $x_{i_1} \geq i_1, x_{i_2} \geq i_2, \dots, x_{i_j} \geq i_j$ và $s = i_1 + i_2 + \dots + i_j$. Khi đó, ta gọi dãy $y$ sao cho $y_i = x_i - i$ nếu $x_i$ là phần tử xấu, ngược lại ta cho $y_i = x_i$. Như vậy bài toán trở thành đếm số dãy $y$ thỏa mãn: $$ y_1 + y_2 + \dots + y_n = k - s \text { và } y_i \geq 0 $$ Áp dụng Chia kẹo Euler, số lượng dãy thỏa mãn trong trường hợp này là $C^{n-1}_{n-1+(k-s)}$

Như vậy ta có cách tính $f(j)$ như sau: Gọi $g(s, j)$ là số cách chọn $j$ số nguyên phân biệt thuộc $[1, n]$ sao cho tổng của chúng là $s$. Khi đó: $$f(j) = \sum_{s = 0}^{k} g(s, j)\times C^{n-1}_{n-1+k-s}$$

Ta nhận thấy do $j$ số nguyên phân biệt nên $j \leq \sqrt{k}$, vì vậy ta có thể tính $g(s, j)$ bằng quy hoạch động trong $O(k\sqrt{k})$ theo công thức: $$ g(s, j) = g(s-j, j) + g(s-j, j-1) - g(s-(n+1), j-1) $$

Giải thích công thức

Tại trạng thái $(s, j)$ - $j$ phần tử có tổng là $s$, ta có hai trường hợp chuyển trạng thái:

$g(s-j, j)$: Tăng tất cả phần tử, mỗi phần tử thêm $1$ đơn vị.
$g(s-j, j-1) - g(s-(n+1), j-1)$: Tăng tất cả phần tử trước đó, mỗi phần tử thêm $1$ đơn vị, và tạo thêm một phần tử mới có giá trị là $1$. Sau đó, ta phải loại đi các trường hợp dãy có phần tử lớn hơn $n$.

Cuối cùng, áp dụng nguyên lí bao hàm loại trừ, ta có công thức cho đáp án như sau: $$ \text{answer} = \sum_{j = 0}^{\sqrt{k}} (-1)^j f(j) $$

Code tham khảo

Hãy xem code khi thực sự cần thiết

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133


// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <class T>
bool maximize(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
void read(T &a) {
	a = 0;
	char c; 
	while (!isdigit(c = getchar())) {}
	do {
		a = a*10 + (c-'0');
	} while (isdigit(c = getchar()));
}

template<class T> 
void write(T a){
	if (a > 9) write(a/10);
	putchar(a%10 + '0');
}

/***End of Template***/
int n, k;
const int N = 1e5+5, SQRT = 500, MOD = 1e9+7;
int fact[2*N], inv[2*N];
int dp[N][SQRT];

void Input() {
	cin >> n >> k;
}

int modPow(int a, int b) {
	int res = 1;
	while (b) {
		if (b&1) res = 1ll*res*a % MOD;
		a = 1ll*a*a%MOD;
		b >>= 1;
	}
	return res;
}

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a-= MOD;
}

void sub(int &a, int b) {
	a -= b;
	if (a < 0) a += MOD;
}

ll minSum(int n) {
	return 1ll*n*(n+1)/2;
}

void prepare() {
	fact[0] = 1;
	FOR(i, 1, 2*N-1) fact[i] = 1ll*fact[i-1]*i % MOD;
	inv[2*N-1] = modPow(fact[2*N-1], MOD-2);
	FORD(i, 2*N-2, 0) inv[i] = 1ll*inv[i+1]*(i+1) % MOD;

	memset(dp, 0, sizeof dp);
	dp[0][0] = 1;
	int sqrt_k = sqrt(k);
	FOR(s, 1, k) for(int i = 1; minSum(i) <= s; ++i) {
		if (s-i >= 0) dp[s][i] = (dp[s-i][i] + dp[s-i][i-1]) % MOD;
		if (s-(n+1) >= 0) sub(dp[s][i], dp[s-(n+1)][i-1]);
	}
	
}

int nCr(int n, int r) {
	if (n < r) return 0;
	return 1ll*fact[n]*inv[r] % MOD * inv[n-r] % MOD;
}

int calc(int j) {
	int ans = 0;
	FOR(s, minSum(j), k) {
		add(ans, 1ll*nCr(n-1+k-s, n-1)*dp[s][j] % MOD);
	} 
	return ans;
}

void Solve() {
	prepare();
	int ans = 0;
	for(int j = 0; minSum(j) <= k; ++j) {
		if (j&1) sub(ans, calc(j));
		else add(ans, calc(j));
	}
	cout << ans;
}	

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	if (fopen("inputf.in", "r")) freopen("inputf.in", "r", stdin);
	Input(), Solve();
	return 0;
}