Free Contest 34 - SHPROB

Xem dạng PDF
Gửi bài giải
Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 3
    YougiTuber  đã bình luận lúc 21, Tháng 4, 2025, 12:25

    Spoil thuật ⚠️

    DP SOS + bao hàm loại trừ

    Gọi dp[mask] là số tập có giá trị AND là mask

    Công thức:

    ~dp[mask] = 2^{cnt[mask]} - dp[super\_mask]~

    Với cnt[mask] là số số có giá trị là mask và super_mask là số thoả mãn mask là tập con của super_mask (mask & super_mask == mask)

    Kết quả

    ~dp[0]~

    Độ phức tạp

    ~O(20 \times 2^{20} + n)~