Lời giải Bài 4 đề thi TS10 2023-24 môn Tin học của Đà Nẵng

Đề bài

Cho mảng $a$ gồm $n$ phần tử nguyên dương và số nguyên dương $k$. Đếm số subsequence của $a$ có tổng bằng $k$.

Giới hạn: $1 \le n, k, a_i \le 10^5$

Link bài: https://lqdoj.edu.vn/problem/23ts10dna4 Cần join link này trước: https://lqdoj.edu.vn/contest/23ts10dna

Lời giải

Lời giải mặc định độc giả đã biết các kiến thức cơ bản về hàm sinh.

Gọi $f_i$ là đáp án với $k = i$, $F(x)$ là hàm sinh của $f_i$. Dễ thấy:

$F(x) = (1 + x^{a_1}) \times (1 + x^{a_2}) \times \dots (1 + x^{a_n})$

Nếu nhân thẳng các đa thức trên bằng FFT, ta sẽ có độ phức tạp $O(nklogn)$, vốn còn chậm hơn thuật vét cạn bằng DP Knapsack $(O(nk))$.

Tuy nhiên, tới đây, ta có một cái trick khá hay, dựa trên nhận xét sau: $ln(a \times b) = ln(a) + ln(b)$

Gọi: $G(x) = ln(F(x))$ $= ln((1 + x^{a_1}) \times (1 + x^{a_2}) \times \dots (1 + x^{a_n}))$ $= ln(1 + x^{a_1}) + ln(1 + x^{a_2}) + \dots + ln(1 + x^{a_n})$

Vậy ta tính $ln(1 + x^k)$ nhu nào? Với Taylor Series, ta có:

$ln(1 + x^k) = \sum_{n = 1}^{\infty} (-1)^{n + 1} \frac{x^{nk}}{n} = x^k - \frac{x^{2k}}{2} + \frac{x^{3k}}{3} - \dots$

Vậy ta có thể tính $G(x)$ trong $O(nlogn)$ đơn giản chỉ là for qua các bội và cộng hệ số vào.

Sau đó, ta có thể tính được $F(x) = e^{G(x)}$.

Đáp án cuối cùng là $[x^k]F(x)$, hay hệ số của $x^k$ trong $F(x)$.

Các bạn có thể xem implement tại đây

Một chút bàn luận

Bài này là một bài rất rất khó với đề ts10, hay thậm chí là đề VOI. Với bài này, trong bối cảnh là kỳ thi offline, không được dùng template và nộp $1$ lần, với những người kỳ cựu nhất và biết cả sol thì việc cài đặt bài này là vô cùng khó.

Tuy nhiên, vét cạn bài này lại rất cơ bản và các bạn nên chắc chắn làm được $O(nk)$.

Chúc các bạn thành công trong việc full đề ts10 ĐN 2023.