Tổng trong tập con

Submit solution
Points: 4 (partial)
Time limit: 1.0s
JAVA11 2.0s
Pypy 3 2.0s
Memory limit: 67M
JAVA11 977M
Pypy 3 977M
Author:
old_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 \le 2*m \le n \le 50, -10^{12} \le S \le 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 \le 40\).

Ví dụ

Đầu vào 1:

5 2 10
1 2 4 8 16

Đầu ra 1:

3

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:

6 3 6
1 1 2 2 3 3

Đầu ra 2:

4

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
      old_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!