TLEoj Contest #07 - Knapsack đơn giản

Điểm: 2300

Thời gian: 1.5s

Python 3 5.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

haiender288

Dạng bài

Chắc hẳn các bạn đã biết về bài toán cái túi, hay knapsack. Bài toán này là một phiên bản khác của bài toán cái túi.

Có $n$ món đồ, món đồ thứ $i$ có cân nặng $a_i$ . An chọn một số món đồ sao cho tổng cân nặng của chúng đúng bằng $m$ và muốn biết rằng có bao nhiêu cách chọn đồ như vậy. Một món đồ có thể chọn $0$ lần, $1$ lần hoặc nhiều hơn $1$ lần, hai cách chọn được gọi là khác nhau nếu có một món đồ chọn nhiều hoặc ít hơn cách chọn kia. Hãy giúp bạn An đếm nhé

Input, Output và Subtasks

Input: (standard input)

Dòng đầu gồm hai số nguyên dương $n$ và $m$ ( $1\leq n\leq 10$ ).
Dòng tiếp theo gồm $n$ số nguyên dương $a_1,a_2,...,a_n$ ( $1\leq a_i\leq 20$ ).

Output: (standard output)

In ra một số là số cách chọn mod $10^9+7$ .

Subtasks

Subtask 1 $(40\%)$ : $m\leq 2000$
Subtask 2 $(20\%)$ : $n=2$ , $m\leq 10^{18}$
Subtask 3 $(40\%)$ : $m\leq 10^{18}$

Sample

Input (standard input)

3 4
1 2 3

Output (standard output)

Bình luận

1

jiangly, 11:03 a.m. 16 Tháng 9, 2023

Knapsack "đơn giản"