Open and Close Interval Trick

Nhóm đang mở và chi phí trả dần

Sắp các giá trị tăng dần. Độ chênh của một nhóm là $\max - \min$, bằng tổng các khoảng $a_{i} - a_{i-1}$ nằm giữa $\min$ và $\max$ của nhóm. Vậy khi đi từ $a_{i-1}$ tới $a_i$, mọi nhóm đang mở (đã có $\min$, chưa có $\max$) cộng thêm đúng $a_i - a_{i-1}$. Với $j$ nhóm đang mở, tổng chi phí tăng $j \cdot (a_i - a_{i-1})$, một con số chỉ phụ thuộc trạng thái. Nếu đề chỉ hỏi tổng không vượt $K$, chiều chi phí bị chặn bởi $K$ dù các giá trị lớn.

Với phần tử $a_i$ và $j$ nhóm đang mở, có bốn lựa chọn: đứng riêng (nhóm một người, mở rồi đóng ngay), mở nhóm mới ($j + 1$), nhập vào một trong $j$ nhóm mà không đóng ($j$ cách), đóng một trong $j$ nhóm bằng chính nó ($j$ cách, còn $j - 1$). Cuối cùng phải không còn nhóm nào mở.

Ví dụChia Nhóm Cân Bằng

Đề. $n \le 200$ học sinh có giá trị tới 500. Đếm số cách chia thành các nhóm sao cho tổng (max − min) của các nhóm không vượt $K \le 1000$, modulo $10^9 + 7$.

Lời giải. Sắp tăng dần. $dp[j][k]$ là số cách khi có $j$ nhóm đang mở và tổng chi phí đã trả là $k$. Trước khi xét học sinh $i \ge 2$, mọi trạng thái nhận thêm $j \cdot (a_i - a_{i-1})$, vượt $K$ thì bỏ. Rồi áp bốn lựa chọn trên. Đáp án là $\sum_k dp[0][k]$. Độ phức tạp $O(n^2 K) = 4 \cdot 10^7$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
ll n, K, a[205], dp[205][1005], nd[205][1005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> K;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    dp[0][0] = 1;
    for (ll i = 1; i <= n; i++) {
        ll gap = i > 1 ? a[i] - a[i - 1] : 0;
        for (ll j = 0; j <= n; j++)
            for (ll k = 0; k <= K; k++) nd[j][k] = 0;
        for (ll j = 0; j < i; j++)
            for (ll k = 0; k <= K; k++) {
                if (!dp[j][k]) continue;
                ll nk = k + j * gap;
                if (nk > K) continue;
                ll v = dp[j][k];
                nd[j][nk] = (nd[j][nk] + v * (j + 1)) % MOD;
                nd[j + 1][nk] = (nd[j + 1][nk] + v) % MOD;
                if (j) nd[j - 1][nk] = (nd[j - 1][nk] + v * j) % MOD;
            }
        for (ll j = 0; j <= n; j++)
            for (ll k = 0; k <= K; k++) dp[j][k] = nd[j][k];
    }
    ll ans = 0;
    for (ll k = 0; k <= K; k++) ans = (ans + dp[0][k]) % MOD;
    cout << ans << '\n';
}

Input3 1
1 2 4

Output2

Hai lựa chọn “đứng riêng” và “nhập vào một nhóm” cùng giữ nguyên $j$, nên gộp thành hệ số $j + 1$.

Đoạn mở trên dãy

Cùng ý tưởng dùng theo vị trí: chọn các đoạn $[l, r]$ để mỗi vị trí được phủ đúng một số lần cho trước. Quét từ trái sang, trạng thái là số đoạn đang mở đi qua vị trí hiện tại. Tại vị trí $i$, số đoạn phủ $i$ bằng số đoạn mở từ trước cộng (có mở đoạn mới tại $i$ hay không); sau đó có thể đóng một trong các đoạn đang phủ $i$, chọn đoạn nào là một hệ số nhân. Nếu đề cấm hai đoạn chung đầu trái hay chung đầu phải, mỗi vị trí mở tối đa một và đóng tối đa một.

Ví dụNhững Đoạn Nâng Mức

Đề. Dãy $n \le 2000$ số và mức $h \le 2000$. Chọn một tập đoạn, mỗi đoạn tăng các phần tử của nó thêm 1, để cả dãy bằng $h$; không hai đoạn chung đầu trái, không hai đoạn chung đầu phải. Đếm số tập, modulo $10^9 + 7$.

Lời giải. Vị trí $i$ phải được phủ đúng $d_i = h - a_i$ lần ($d_i < 0$ thì vô nghiệm). $dp[j]$ là số cách khi $j$ đoạn còn mở sau vị trí trước. Tại $i$: cần mở thêm $s = d_i - j \in \{0, 1\}$ đoạn; rồi không đóng (còn $d_i$ đoạn mở) hoặc đóng một trong $d_i$ đoạn (còn $d_i - 1$). Đáp án là $dp[0]$ sau vị trí $n$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
ll n, h, a[2005], dp[2005], nd[2005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> h;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    dp[0] = 1;
    for (ll i = 1; i <= n; i++) {
        ll d = h - a[i];
        for (ll j = 0; j <= h; j++) nd[j] = 0;
        if (d >= 0)
            for (ll j = 0; j <= d; j++) {
                if (!dp[j] || d - j > 1) continue;
                nd[d] = (nd[d] + dp[j]) % MOD;
                if (d) nd[d - 1] = (nd[d - 1] + dp[j] * d) % MOD;
            }
        for (ll j = 0; j <= h; j++) dp[j] = nd[j];
    }
    cout << dp[0] << '\n';
}

Input2 1
0 0

Output2

Chèn giá trị tăng dần thành các thành phần

Đếm hoán vị có ràng buộc giữa các phần tử kề nhau (zích zắc, không hơn kém 1, tổng chênh lệch nhỏ): dựng hoán vị bằng cách chèn các giá trị $1, 2, \dots, n$ theo thứ tự tăng dần. Ở mỗi thời điểm, những giá trị đã chèn tạo thành một số khối (thành phần liên thông) sẽ nằm theo đúng thứ tự trái phải trong hoán vị cuối, nhưng khoảng cách giữa các khối chưa biết, sẽ được lấp bởi các giá trị lớn hơn. Giá trị mới $i$ có ba lựa chọn:

• tạo một khối mới ở một khe giữa hoặc hai bên các khối hiện có;
• nối vào đầu trái hay đầu phải của một khối;
• đứng giữa hai khối liền nhau và gộp chúng.

Vì $i$ lớn hơn mọi giá trị đã chèn, hàng xóm chèn trước luôn nhỏ hơn nó, hàng xóm chèn sau luôn lớn hơn. Nên vai trò của $i$ biết ngay khi chèn: gộp hai khối thì cả hai hàng xóm nhỏ hơn, $i$ là đỉnh; tạo khối mới thì cả hai hàng xóm (chèn sau) lớn hơn, $i$ là đáy; nối vào một đầu thì một hàng xóm nhỏ, một hàng xóm lớn. Điểm đầu và điểm cuối cố định của hoán vị là khối đặc biệt: không gì được chèn vào bên trái điểm đầu hay bên phải điểm cuối.

Ví dụĐường Đi Zích Zắc

Đề. $N \le 2000$ ô. Đếm các thứ tự thăm mọi ô một lần, bắt đầu ở $s$, kết thúc ở $e$, mà từ bước thứ hai hướng đi luân phiên (mỗi ô ở giữa là đỉnh cục bộ hoặc đáy cục bộ), modulo $10^9 + 7$.

Lời giải. Chèn $1..N$ tăng dần, $dp[i][j]$ là số cách sau khi chèn $i$ với $j$ khối. Mỗi giá trị ở giữa phải là đỉnh hoặc đáy, nên $i \ne s, e$ chỉ được tạo khối mới (thành đáy) hoặc gộp hai khối (thành đỉnh); nối vào một đầu cho nó một hàng xóm nhỏ và một lớn, sai luật. Còn $s$ và $e$ chỉ có một hàng xóm: chúng tạo khối mới ở đầu mút hoặc nối vào khối ở đầu mút tương ứng. Với $i \ne s, e$: tạo khối mới có $j - [i > s] - [i > e]$ khe hợp lệ ($j$ là số khối sau khi chèn, không chen trái $s$ hay phải $e$ đã có); gộp có $j$ cách chọn cặp khối liền nhau trong $j + 1$ khối. Đáp án $dp[N][1]$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
ll n, s, e, dp[2005][2005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s >> e;
    dp[0][0] = 1;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= i; j++) {
            if (i == s || i == e) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            else {
                ll slots = j - (i > s) - (i > e);
                if (slots > 0) dp[i][j] = dp[i - 1][j - 1] * slots % MOD;
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1] * j) % MOD;
            }
        }
    cout << dp[n][1] << '\n';
}

Input3 1 2

Output1

Thành phần cùng chi phí khoảng cách

Gộp hai ý trên: đếm hoán vị có $\sum |f_i - f_{i+1}| \le L$. Chèn giá trị theo thứ tự tăng dần thành các khối. Mỗi khối có hai đầu còn trống (trừ đầu đã cố định là đầu mút của cả hoán vị); mỗi đầu trống sau này sẽ nối với một giá trị lớn hơn, nên khi giá trị tăng từ $A_{i-1}$ lên $A_i$, mỗi đầu trống góp thêm đúng $A_i - A_{i-1}$ vào tổng. Với $j$ khối và $l$ đầu mút đã cố định ($l \le 2$), số đầu trống là $2j - l$, chi phí tăng $(2j - l)(A_i - A_{i-1})$: lại là “số đang mở nhân khoảng cách”. Trạng thái gồm số khối, chi phí đã trả và số đầu mút đã cố định.

Ví dụDãy Độ Cao Êm

Đề. $N \le 100$ độ cao khác nhau tới 1000. Đếm hoán vị có $\sum |f_i - f_{i+1}| \le L \le 1000$, modulo $10^9 + 7$.

Lời giải. Sắp tăng dần và chèn dần các độ cao từ nhỏ tới lớn. Trạng thái $dp[j][k][l]$: đang có $j$ khối (đoạn liên tiếp của hoán vị cuối cùng, chưa biết vị trí tương đối), chi phí đã trả $k$, và $l$ đầu mút của cả hoán vị đã cố định. Mẹo trả chi phí trước: khi chuyển từ $A_{i-1}$ lên $A_i$, mỗi “đầu trống” của các khối (chỗ còn ghép thêm số lớn hơn) chắc chắn sẽ nối với một số $\ge A_i$, nên mọi trạng thái cộng $(2j - l)(A_i - A_{i-1})$ ngay. Riêng $N = 1$ đáp án là 1.

Bước 1: trạng thái đầu. Số nhỏ nhất đứng thành một khối: không cố định đầu mút nào (1 cách), hoặc cố định làm một trong hai đầu mút (2 cách).

dp[1][0][0] = 1;
dp[1][0][1] = 2;

Bước 2: cộng chi phí trước. Vượt $L$ thì bỏ trạng thái.

ll nk = k + (2 * j - l) * (A[i] - A[i - 1]);
if (nk > L) continue;

Bước 3: năm cách đặt $A_i$. Khối mới ở giữa ($j + 1 - l$ khe); khối mới làm đầu mút ($2 - l$ cách, $l$ tăng); nối vào một đầu trống của một khối ($2j - l$ cách); nối ra ngoài cùng và cố định làm đầu mút ($2 - l$ cách); gộp hai khối liền nhau ($j - 1$ cách).

if (j + 1 - l > 0) add(nd[j + 1][nk][l], v * (j + 1 - l));
if (l < 2) add(nd[j + 1][nk][l + 1], v * (2 - l));
if (2 * j - l > 0) add(nd[j][nk][l], v * (2 * j - l));
if (l < 2) add(nd[j][nk][l + 1], v * (2 - l));
if (j >= 2) add(nd[j - 1][nk][l], v * (j - 1));

Đáp án là tổng $dp[1][k][2]$ trên mọi $k \le L$: còn đúng một khối, cả hai đầu mút đã cố định.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
ll n, L, A[105], dp[105][1005][3], nd[105][1005][3];

void add(ll &x, ll v) {
    x = (x + v) % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> L;
    for (ll i = 1; i <= n; i++) cin >> A[i];
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    sort(A + 1, A + n + 1);
    dp[1][0][0] = 1;
    dp[1][0][1] = 2;
    for (ll i = 2; i <= n; i++) {
        for (ll j = 0; j <= i; j++)
            for (ll k = 0; k <= L; k++)
                for (ll l = 0; l < 3; l++) nd[j][k][l] = 0;
        for (ll j = 1; j < i; j++)
            for (ll k = 0; k <= L; k++)
                for (ll l = 0; l < 3; l++) {
                    ll v = dp[j][k][l];
                    if (!v) continue;
                    ll nk = k + (2 * j - l) * (A[i] - A[i - 1]);
                    if (nk > L) continue;
                    if (j + 1 - l > 0) add(nd[j + 1][nk][l], v * (j + 1 - l));
                    if (l < 2) add(nd[j + 1][nk][l + 1], v * (2 - l));
                    if (2 * j - l > 0) add(nd[j][nk][l], v * (2 * j - l));
                    if (l < 2) add(nd[j][nk][l + 1], v * (2 - l));
                    if (j >= 2) add(nd[j - 1][nk][l], v * (j - 1));
                }
        for (ll j = 0; j <= i; j++)
            for (ll k = 0; k <= L; k++)
                for (ll l = 0; l < 3; l++) dp[j][k][l] = nd[j][k][l];
    }
    ll ans = 0;
    for (ll k = 0; k <= L; k++) add(ans, dp[1][k][2]);
    cout << ans << '\n';
}

Input3 2
1 2 3

Output2

$O(N^2 L)$, khoảng $10^7$ trạng thái mỗi tầng nhân 3.