Bộ Vũ Khí Tốt (Codeforces 145C

Nguồn: Codeforces 145C (Lucky Subsequence) Độ khó: Khá Quy hoạch động Tổ hợp Modulo Map

Đề bài

Hải là một chiến binh của một bộ lạc thời tiền sử. Nhiệm vụ của anh ta là đột nhập vào lãnh thổ của các bộ lạc khác và triệt hạ đi các thủ lĩnh bộ lạc này. Trong một lần hành động thành công, Hải đã cướp được $N$ vũ khí. Theo thông tin của nhà tiên tri cùng bộ lạc, mỗi vũ khí có đánh một con số, vũ khí thứ $i$ sẽ mang số $a_i$. Được biết các vũ khí có mang số được tạo bởi từ các chữ số $4$, $7$ (ví dụ: $4, 7, 44, 47, 74, 77, 444, 447, 474, 477, \ldots$) là các vũ khí đã bị nguyền rủa. Nhà tiên tri đã cho Hải biết rằng, một bộ vũ khí tốt là bộ vũ khí không chứa hai hay nhiều vũ khí bị nguyền rủa có cùng giá trị.

Trong số các vũ khí mà Hải mang về được, Hải không biết được rằng có bao nhiêu bộ vũ khí tốt có đúng $K$ vũ khí.

Bạn được cho một dãy số $a$ chứa các số tương ứng với các số trong bộ vũ khí của Hải lấy được. Nhiệm vụ của bạn là tính xem có bao nhiêu bộ vũ khí tốt có $K$ vũ khí mà Hải lấy được theo lời khuyên của nhà tiên tri. Hai bộ trang bị khác nhau nếu có ít nhất 1 vũ khí mà bộ còn lại không có. Vì số bộ vũ khí có thể rất lớn nên hãy đưa ra kết quả với phép chia lấy dư cho $1000000007$ $(10^9 + 7)$.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên $N, K$ $(1 \le K \le N \le 10^5)$.
• Dòng thứ hai chứa $N$ số nguyên $a_i$ $(1 \le a_i \le 10^9)$, là dãy các số $a$.

Dữ liệu ra:

• Số bộ vũ khí tốt có $K$ vũ khí.

Ví dụ 1 – input

3 2
10 10 10

Ví dụ 1 – output

3

Ví dụ 2 – input

4 2
4 4 7 7

Ví dụ 2 – output

4

Giải thích: Trường hợp đầu tiên: do không có vũ khí nào bị nguyền rủa nên ta có thể chọn bất cứ vũ khí nào vào bộ trang bị.

Lời mở đầu

Hôm qua có một bạn trong nhóm comment nhờ mình hỗ trợ bài tập này, bạn ấy hỏi: "Thưa anh có cách nào giải bài toán tìm tổ hợp một cách nhanh nhất không ạ :((( Em gần xong bài này nhưng đoạn tìm tổ hợp của em chưa tối ưu :((". Mình thấy bài này cũng hay nên chia sẻ lên để anh em cùng xem và thử sức, rồi viết luôn bài giải chi tiết theo hướng mình đã trả lời bạn ấy. Hi vọng mang đến giá trị cho anh em 😇.

Bài này chính là bài Lucky Subsequence (Codeforces 145C) được "Việt hoá" lại: số bị nguyền rủa chính là lucky number, bộ vũ khí là dãy con (chọn theo chỉ số). Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link dưới đây nha:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ:

• Ví dụ 1: ba vũ khí đều mang số $10$ (có chữ số $1$, $0$ nên không bị nguyền rủa). Số không bị nguyền rủa thì trùng nhau thoải mái, nên chọn 2 trong 3 vũ khí kiểu gì cũng được: $C_3^2 = 3$ bộ: $\{1, 2\}, \{1, 3\}, \{2, 3\}$ (đánh số theo vị trí).
• Ví dụ 2: dãy $4, 4, 7, 7$ toàn số bị nguyền rủa. Bộ 2 vũ khí không được có hai số $4$ hay hai số $7$, nên bộ phải gồm đúng một số $4$ và một số $7$: có $2$ cách chọn số $4$ (vị trí 1 hoặc 2) và $2$ cách chọn số $7$ (vị trí 3 hoặc 4) ⇒ $2 \times 2 = 4$ bộ: $\{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}$.

Lưu ý đề

Hai bộ khác nhau là khác nhau về vũ khí (vị trí), không phải về giá trị. Vì thế ở ví dụ 1 dù cả 3 số đều là $10$ vẫn đếm ra 3 bộ.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn mọi bộ · O(2^N · N)Cách 2QHĐ + tổ hợp · O(sz(b)² + N)

Cách 1Vét cạn mọi bộ vũ khí – O(2^N · N)

Cách "làm theo đề" đơn giản nhất: duyệt mọi tập con (bitmask) của $N$ vũ khí, chỉ giữ những tập có đúng $K$ phần tử, rồi kiểm tra trong tập đó các số bị nguyền rủa có bị trùng không (dùng set). Tập nào không trùng thì đếm.

Cách này chỉ chạy được với $N$ khoảng $20$ đổ lại, mình đưa vào để các bạn hiểu đề và dùng làm code đối chiếu (mình đã dùng chính code này để kiểm tra cách 2).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

bool isLucky(long long x){
    while(x > 0){
        int d = x % 10;
        if(d != 4 && d != 7) return false;
        x /= 10;
    }
    return true;
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    long long ans = 0;
    for(int mask = 0; mask < (1 << n); mask++){
        if(__builtin_popcount(mask) != k) continue;
        set<long long> used;
        bool ok = true;
        for(int i = 0; i < n; i++){
            if(!(mask >> i & 1) || !isLucky(a[i])) continue;
            if(used.count(a[i])) { ok = false; break; }
            used.insert(a[i]);
        }
        if(ok) ans++;
    }
    cout << ans % MOD;
    return 0;
}

MOD = 10**9 + 7

def is_lucky(x):
    while x > 0:
        if x % 10 not in (4, 7):
            return False
        x //= 10
    return True

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for mask in range(1 << n):
    if bin(mask).count('1') != k:
        continue
    used = set()
    ok = True
    for i in range(n):
        if not (mask >> i & 1) or not is_lucky(a[i]):
            continue
        if a[i] in used:
            ok = False
            break
        used.add(a[i])
    if ok:
        ans += 1
print(ans % MOD)

Không gian$O(N)$

Thời gian$O(2^N \cdot N)$

Chỉ dùng cho N nhỏ

Với $N = 10^5$ thì $2^N$ là con số khổng lồ, chắc chắn TLE. Ta cần nhìn ra tính chất đặc biệt của số bị nguyền rủa.

Cách 2Quy hoạch động trên các số nguyền rủa + tổ hợp – O(sz(b)² + N)

Nhận xét quan trọng: số nguyền rủa khác nhau rất ít

Để ý như sau: giá trị số nguyền rủa khác nhau không có nhiều. Do $a_i \le 10^9$ nên $a_i$ có tối đa 9 chữ số, thì số lượng số bị nguyền rủa khác nhau có 1 chữ số là $2$ ($4, 7$), có 2 chữ số là $4$ số, có 3 chữ số là $8$ số, ..., có 9 chữ số là $2^9 = 512$ số. Như vậy số lượng số bị nguyền rủa khác nhau là:

Số lượng số nguyền rủa khác nhau

$2 + 4 + 8 + 16 + \ldots + 2^9 = 1022 \approx 1024$

Và bởi vì ta không được phép chọn 2 số nguyền rủa giống nhau, nên mỗi giá trị nguyền rủa chỉ được chọn tối đa 1 lần. Ví dụ giả sử trong dãy có 10 số $4$, 20 số $44$, thì có 10 cách chọn một số $4$, 20 cách chọn một số $44$.

Tách dãy a thành 2 loại

Ta hãy tách riêng dãy $a$ ra gồm 2 loại: dãy gồm các số nguyền rủa và dãy gồm các số không bị nguyền rủa.

• Với dãy không bị nguyền rủa, thực tế ta không cần biết dãy số đó gồm những số nào (trùng thoải mái mà). Ta chỉ cần quan tâm dãy số đó có bao nhiêu số thôi. Gọi số lượng số không bị nguyền rủa là count.
• Với dãy bị nguyền rủa, ta đếm số lượng của từng giá trị: với mỗi số bị nguyền rủa $x$, gọi cnt[x] là số lượng số $x$ có trong dãy. Ví dụ dãy $a = [4, 4, 2, 5, 4, 77]$ thì cnt[4] = 3, cnt[77] = 1 (và count = 2 ứng với hai số $2$, $5$).

Ta lưu các cặp <số bị nguyền rủa, số lượng> vào một dãy $b$. Như ví dụ trên thì $b = [\langle 4, 3\rangle, \langle 77, 1\rangle]$. Kích thước $sz(b) \le 1022$.

Quy hoạch động chọn số nguyền rủa

Vì mỗi số bị nguyền rủa chỉ được phép chọn 1 lần, ta gọi $f[i][j]$ là số cách chọn ra $j$ số bị nguyền rủa khi ta xét đến phần tử thứ $i$ của dãy $b$.

• Bài toán cơ sở: $f[0][0] = 1$ (chưa xét gì, chọn 0 số: 1 cách).
• Quy hoạch động: với $f[i][j]$ hiện tại $\gt 0$, ta xét số bị nguyền rủa thứ $i + 1$:
  • nếu không chọn số nguyền rủa thứ $i + 1$ thì $f[i + 1][j] \mathrel{+}= f[i][j]$;
  • nếu chọn số nguyền rủa thứ $i + 1$ thì có b[i + 1].second cách chọn ra 1 vũ khí mang số đó: $f[i + 1][j + 1] \mathrel{+}= f[i][j] \cdot b[i + 1].second$.

Ghép với số không bị nguyền rủa

Sau khi quy hoạch động xong, ta có bảng $f$. Bây giờ, nếu ta chọn $j$ số bị nguyền rủa thì đồng nghĩa với việc $k - j$ số còn lại sẽ là số không bị nguyền rủa. Số cách chọn $k - j$ số không bị nguyền rủa trong count số là $C(k - j, count)$ (chọn $k - j$ phần tử từ count phần tử). Còn số cách chọn $j$ số bị nguyền rủa là $f[sz(b)][j]$.

Công thức đáp án

$\text{ans} = \displaystyle\sum_{j=0}^{\min(k,\ sz(b))} f[sz(b)][j] \cdot C(k - j,\ count)$

Thử với $a = [4, 4, 2, 5, 4, 77]$, $k = 3$: $b = [\langle 4,3\rangle, \langle 77,1\rangle]$, $count = 2$. Bảng QHĐ: $f[1][0] = 1,\ f[1][1] = 3$; rồi $f[2][0] = 1,\ f[2][1] = 3 + 1 = 4,\ f[2][2] = 3$. Đáp án $= 1 \cdot C(3, 2) + 4 \cdot C(2, 2) + 3 \cdot C(1, 2) = 0 + 4 + 6 = 10$.

Các bạn nhập dãy rồi bấm Tiếp để xem từng bước tách dãy, điền bảng $f$ và cộng đáp án:

K Dãy a

Ví dụ nhanh:

Tính tổ hợp C nhanh

Đây chính là chỗ bạn học viên hỏi "tìm tổ hợp nhanh nhất". Vì $count \le N \le 10^5$, ta tính trước giai thừa fact[i] = i! mod (10^9 + 7) và nghịch đảo giai thừa inv[i]. Do $10^9 + 7$ là số nguyên tố, theo định lý Fermat nhỏ: $inv[n] = (n!)^{10^9 + 5} \bmod (10^9 + 7)$ (tính bằng lũy thừa nhanh), rồi lùi dần $inv[i - 1] = inv[i] \cdot i$. Khi đó mỗi lần tính:

Tổ hợp O(1)

$C(k, n) = \dfrac{n!}{k!\,(n - k)!} = fact[n] \cdot inv[k] \cdot inv[n - k] \bmod (10^9 + 7)$, và $C(k, n) = 0$ khi $k \lt 0$ hoặc $k \gt n$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int MAXN = 100005;
long long fact[MAXN], inv[MAXN];
long long f[1100][1100];

bool isLucky(long long x){
    while(x > 0){
        int d = x % 10;
        if(d != 4 && d != 7) return false;
        x /= 10;
    }
    return true;
}

long long power(long long a, long long b){
    long long res = 1;
    while(b > 0){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

long long C(int k, int n){ // số cách chọn k phần tử từ n phần tử
    if(k < 0 || k > n) return 0;
    return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int main(){
    int n, k;
    cin >> n >> k;
    map<long long, int> cnt;
    int count = 0;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        if(isLucky(x)) cnt[x]++;
        else count++;
    }
    vector<pair<long long, int>> b(1); // b[0] bỏ trống, b đánh số từ 1
    for(auto p : cnt) b.push_back(p);
    int m = b.size() - 1;
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    inv[n] = power(fact[n], MOD - 2);
    for(int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
    f[0][0] = 1;
    for(int i = 0; i < m; i++){
        for(int j = 0; j <= i; j++){
            if(f[i][j] == 0) continue;
            f[i + 1][j] = (f[i + 1][j] + f[i][j]) % MOD;
            f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * b[i + 1].second) % MOD;
        }
    }
    long long ans = 0;
    for(int j = 0; j <= min(k, m); j++){
        ans = (ans + f[m][j] * C(k - j, count)) % MOD;
    }
    cout << ans;
    return 0;
}

import sys
MOD = 10**9 + 7

def is_lucky(x):
    while x > 0:
        if x % 10 not in (4, 7):
            return False
        x //= 10
    return True

data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
cnt = {}
count = 0
for i in range(n):
    x = int(data[2 + i])
    if is_lucky(x):
        cnt[x] = cnt.get(x, 0) + 1
    else:
        count += 1
b = [(0, 0)] + sorted(cnt.items())  # b[0] bỏ trống, b đánh số từ 1
m = len(b) - 1

fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD
inv = [1] * (n + 1)
inv[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n, 0, -1):
    inv[i - 1] = inv[i] * i % MOD

def C(k, n):  # số cách chọn k phần tử từ n phần tử
    if k < 0 or k > n:
        return 0
    return fact[n] * inv[k] % MOD * inv[n - k] % MOD

f = [[0] * (m + 2) for _ in range(m + 1)]
f[0][0] = 1
for i in range(m):
    cur, nxt, c = f[i], f[i + 1], b[i + 1][1]
    for j in range(i + 1):
        if cur[j] == 0:
            continue
        nxt[j] = (nxt[j] + cur[j]) % MOD
        nxt[j + 1] = (nxt[j + 1] + cur[j] * c) % MOD

ans = 0
for j in range(min(k, m) + 1):
    ans = (ans + f[m][j] * C(k - j, count)) % MOD
print(ans)

C++▶ Chạy tay từng dòng codeTách số nguyền rủa ra map cnt, QHĐ f[i][j] trên dãy b, rồi cộng f[m][j]·C(k − j, count).

Dữ liệu vào (stdin) – sửa thoải mái4 2 4 4 7 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3const long long MOD = 1e9 + 7;

4const int MAXN = 100005;

5long long fact[MAXN], inv[MAXN];

6long long f[1100][1100];

7

8bool isLucky(long long x){

9 while(x > 0){

10 int d = x % 10;

11 if(d != 4 && d != 7) return false;

12 x /= 10;

13 }

14 return true;

15}

16

17long long power(long long a, long long b){

18 long long res = 1;

19 while(b > 0){

20 if(b & 1) res = res * a % MOD;

21 a = a * a % MOD;

22 b >>= 1;

23 }

24 return res;

25}

26

27long long C(int k, int n){ // số cách chọn k phần tử từ n phần tử

28 if(k < 0 || k > n) return 0;

29 return fact[n] * inv[k] % MOD * inv[n - k] % MOD;

30}

31

32int main(){

33 int n, k;

34 cin >> n >> k;

35 map<long long, int> cnt;

36 int count = 0;

37 for(int i = 0; i < n; i++){

38 long long x;

39 cin >> x;

40 if(isLucky(x)) cnt[x]++;

41 else count++;

42 }

43 vector<pair<long long, int>> b(1); // b[0] bỏ trống, b đánh số từ 1

44 for(auto p : cnt) b.push_back(p);

45 int m = b.size() - 1;

46 fact[0] = 1;

47 for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;

48 inv[n] = power(fact[n], MOD - 2);

49 for(int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;

50 f[0][0] = 1;

51 for(int i = 0; i < m; i++){

52 for(int j = 0; j <= i; j++){

53 if(f[i][j] == 0) continue;

54 f[i + 1][j] = (f[i + 1][j] + f[i][j]) % MOD;

55 f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * b[i + 1].second) % MOD;

56 }

57 }

58 long long ans = 0;

59 for(int j = 0; j <= min(k, m); j++){

60 ans = (ans + f[m][j] * C(k - j, count)) % MOD;

61 }

62 cout << ans;

63 return 0;

64}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng fact, inv cỡ $N$ và bảng $f$ cỡ $sz(b)^2 \approx 1022^2$: $O(sz(b)^2 + N)$.
• Thời gian: đọc và phân loại $N$ số (mỗi số kiểm tra tối đa 10 chữ số, đưa vào map), tính giai thừa $O(N)$, QHĐ $O(sz(b)^2)$, cộng đáp án $O(sz(b))$. Tổng cộng $O(sz(b)^2 + N)$. Độ phức tạp này đẹp vì $sz(b)$ là số lượng số bị nguyền rủa khác nhau và $sz(b) \le 1022$.

Không gian$O(sz(b)^2 + N)$

Thời gian$O(sz(b)^2 + N)$

Coi chừng tràn số

f[i][j] * b[i + 1].second có thể tới cỡ $10^9 \cdot 10^5$, nên phải dùng long long và lấy dư ngay sau mỗi phép nhân. Tương tự với fact[n] * inv[k] % MOD * inv[n - k] % MOD: phải % MOD sau mỗi lần nhân, nhân liền 3 số là tràn.

Đừng quên trường hợp k − j > count

Nếu số số thường không đủ để bù cho đủ $k$ vũ khí thì $C(k - j, count) = 0$, hàm C phải trả về $0$ chứ không được truy cập inv với chỉ số âm.

Ghi chú của mình: code C++ và Python của cả 2 cách đã chạy đúng 2 test của đề; cách 2 được so với code vét cạn (cách 1) trên 400 bộ test ngẫu nhiên nhỏ ($N \le 14$, nhiều số nguyền rủa trùng nhau) – khớp hết. Với $N = 10^5$ chứa đủ cả $1022$ số nguyền rủa khác nhau, cách 2 bản C++ chạy khoảng 0.06 giây, bản Python khoảng 0.5 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇