Tổng Trên Mọi Tập Con

Buổi 23 — Thao tác bit
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho mảng $f$ gồm $2^N$ phần tử (đánh số $0$ đến $2^N - 1$). Với mỗi mask $m$ từ $0$ đến $2^N - 1$, hãy tính: \[g(m) = \sum_{s \subseteq m} f(s)\] trong đó $s \subseteq m$ nghĩa là $s \text{ AND } m = s$. In ra tất cả giá trị $g(m)$ modulo $10^9 + 7$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $2^N$ số nguyên $f(0), f(1), \ldots, f(2^N - 1)$.
Dữ liệu ra
  • In ra $2^N$ số nguyên $g(0), g(1), \ldots, g(2^N - 1)$, cách nhau bởi dấu cách.
Ví dụ
Input Output
2
1 2 3 4
1 3 4 10
Giới hạn
  • $1 \le N \le 20$
  • $0 \le f(i) \le 10^9$
Draft saved