Đếm các tập con


Submit solution

Points: 3 (partial)
Time limit: 0.1s
JAVA11 1.0s
Python 3 1.0s
Memory limit: 98M
JAVA11 977M
Python 3 977M

Author:
Problem type
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 \(S\) là một tập hợp các số tự nhiên và số tự nhiên \(m\); đếm số lượng tập con phân biệt của \(S\) (trừ tập rỗng) mà tổng các phần tử trong mỗi tập con đó bằng \(m\).

Đầu vào

Dòng đầu gồm số tự nhiên \(n\) \((1 \le n \le 1000)\) và số tự nhiên \(m\) \((0 \le m \le 1000)\).

Dòng tiếp theo gồm \(n\) số tự nhiên trong đoạn \([0, 10^9]\) là các phần tử của tập hợp.

Ghi chú: \(n\) số tự nhiên nhập vào đảm bảo đôi một phân biệt.

Đầu ra

Một số tự nhiên duy nhất là số lượng tập con cần tìm.

Chú ý: Kết quả lấy mod không âm cho \(10^9 + 7\).

Ví dụ

Đầu vào:

5 5
1 2 3 4 5

Đầu ra:

3

Giải thích: Có 3 tập con có tổng bằng 5 là \(\{1, 4\}\), \(\{2, 3\}\), \(\{5\}\).

.

QDUY

Comments


  • 0
    02200123  commented on April 13, 2023, 8:00 a.m. edited

    mình 1 vòng for mà vẫn bị tle

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class demcactapcon {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n,m,temp;
            Map<Integer,Integer> map = new HashMap<>();
            n = sc.nextInt();
            m = sc.nextInt();
            int result = 0;
            for(int i = 0;i < n; i++)
            {
                temp = sc.nextInt();
                if(temp == m)
                    result +=1;
                else
                    if(map.get(m - temp) != null)
                        result +=1;
                map.put(temp,1);
            }
            System.out.println(result);
        }
    }

    • 0
      creator  commented on April 13, 2023, 7:37 p.m.

      Mình đã bổ sung thêm nn java, bạn xem lại bài nộp của nhé.


      • 0
        02200123  commented on April 14, 2023, 1:59 a.m.

        ok mình cảm ơn nhé


  • 0
    ToMinhTien_CNTT4_K62  commented on July 7, 2022, 9:20 a.m.

    Giới hạn thời gian có 0.1s mà 2 for vẫn AC :v