Tổng trong tập con

Points: 4 (partial)

Time limit: 1.0s

JAVA11 2.0s

Pypy 3 2.0s

Memory limit: 67M

JAVA11 977M

Pypy 3 977M

Author:

creator

Problem types

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Cho dãy số có $n$ phần tử: $a_{1}, a_{2}, . ., a_{n}$ và số nguyên $m$ , số nguyên dương $S$ ; bạn hãy đếm xem có bao nhiêu cách chọn ra một dãy con có $m$ phần tử mà không có hai phần tử nào nằm liên tiếp trong dãy ban đầu, đồng thời tổng các phần tử trong dãy con đã chọn không vượt quá $S$ .

Đầu vào

Dòng đầu tiên chứa số nguyên ba số nguyên $n$ , $m$ và $S$ $(1 \leq 2 * m \leq n \leq 50, - 10^{12} \leq S \leq 10^{12})$ .

Dòng tiếp theo chứa $n$ số nguyên có giá trị tuyệt đối không vượt quá $10^{12}$ , các phần tử trong dãy số.

Ghi chú: Bạn hãy dùng kiểu số nguyên $64$ bit để nhập dữ liệu.

Đầu ra

Một số tự nhiên duy nhất là kết quả bài toán, lấy số dư khi chia cho $10^{9} + 7$ .

Subtask

$30 %$ số test có $n \leq 40$ .

Ví dụ

Đầu vào 1:

Copy

5 2 10
1 2 4 8 16

Đầu ra 1:

Copy

Giải thích: Các dãy con thỏa mãn đề bài là $(1, 4), (1, 8), (2, 8)$ .

Đầu vào 2:

Copy

6 3 6
1 1 2 2 3 3

Đầu ra 2:

Copy

Giải thích: Các dãy con thỏa mãn đề bài là: $(1, 2, 3)$ ( $4$ dãy như vậy).

QDUY

Comments

0

z3r0_l0v3 commented on Sept. 21, 2023, 7:44 a.m.

Bài này làm kiểu gì thế mn?

0

creator commented on Sept. 21, 2023, 10:11 a.m.

Bạn sử dụng kĩ thuật meet-in-the-middle: chia dãy số ban đầu ra hai dãy con các số liên tiếp đồ dài như nhau, giải cho từng dãy con rồi ghép lại đếm kết quả.

0

z3r0_l0v3 commented on Sept. 22, 2023, 8:20 a.m.

Tks. AC!