Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Tổng trên mọi tập con

    Cho mảng aaa có 2n2^n2n phần tử, đánh chỉ số từ 000 đến 2n−12^n - 12n−1. Với mỗi chỉ số maskmaskmask (xem như một mặt nạ bit nnn bit), hãy tính F[mask]=∑sub⊆maska[sub]F[mask] = \sum_{sub \subseteq mask} a[sub]F[mask]=∑sub⊆mask​a[sub] tức tổng a[sub]a[sub]a[sub] trên mọi tập con subsubsub của maskmaskmask (kể cả sub=masksub = masksub=mask và sub=0sub = 0sub=0).

    In kết quả theo modulo 109+710^9+7109+7. Sử dụng kỹ thuật Sum over Subsets (SOS DP) chạy trong O(n⋅2n)O(n \cdot 2^n)O(n⋅2n).

    • Định dạng đầu vào:

      Dòng đầu chứa nnn. Dòng thứ hai chứa 2n2^n2n số nguyên không âm a[0],a[1],…,a[2n−1]a[0], a[1], \dots, a[2^n-1]a[0],a[1],…,a[2n−1].

    • Ràng buộc đầu vào:

      0≤n≤200 \le n \le 200≤n≤20, 0≤a[i]≤1090 \le a[i] \le 10^90≤a[i]≤109.

    • Định dạng đầu ra:

      In 2n2^n2n số F[0],F[1],…,F[2n−1]F[0], F[1], \dots, F[2^n-1]F[0],F[1],…,F[2n−1] trên một dòng, cách nhau bởi dấu cách, lấy modulo 109+710^9+7109+7.

    Ví dụ:

    Đầu vào:

    2
1 2 3 4

    Đầu ra:

    1 3 4 10

    Giải thích:

    Với mask=3 (nhị phân 11), các tập con là 00,01,10,11 nên F[3]=1+2+3+4=10. Với mask=1 chỉ có tập con 00,01 nên F[1]=1+2=3; mask=2 cho F[2]=1+3=4; mask=0 cho F[0]=1.

    Đang tải editor...