## Đề 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](https://codeforces.com/blog/entry/77468)**.

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](https://vnoi.info/wiki/algo/trick/FFT.md)**, 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](https://vi.wikipedia.org/wiki/Chu%E1%BB%97i_Taylor#L%C3%B4garit_t%E1%BB%B1_nhi%C3%AAn)**, 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](https://ideone.com/2M4bev)**

## 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.