Đếm trên các tập con
Submit solution
Points:
4 (partial)
Time limit:
1.0s
JAVA11
2.0s
Python 3
2.0s
Memory limit:
98M
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 tập hợp \(S\) có \(n\) phần tử. Có bao nhiêu cách chọn ra các tập con của \(S\) (các hoán vị chỉ tính một lần) sao cho hợp của các tập con đã chọn bằng \(S\) ?
Ví dụ: Xét \(S = \{a\}\) có các tập con \(\emptyset\) và \(\{a\}\), có 2 cách chọn thỏa mãn đề bài là \(\{a\}\) và \(\{\emptyset, a\}\), cách chọn \(\{\emptyset, a\}\) và \(\{a, \emptyset\}\) là như nhau.
Đầu vào
Một số tự nhiên duy nhất \(n\) \((1 \le n \le 13)\).
Đầu ra
Một số tự nhiên duy nhất là kết quả bài toán, lấy mod không âm cho \(10^9 + 7\).
Ví dụ
Đầu vào:
2Đầu ra:
10
Comments
Ta có đánh giá: với tập có n phần tử kết quả của bài toán lớn hơn hoặc bằng \(2^{2^n - 1}\).