Tích chập tập con
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho số nguyên $N$ và hai mảng $F, G$ có độ dài $2^N$ (chỉ số từ $0$ đến $2^N - 1$). Tích chập tập con (Subset Convolution) của $F$ và $G$ là mảng $H$ độ dài $2^N$ được định nghĩa như sau: \[H[S] = \sum_{T \subseteq S} F[T] \cdot G[S \setminus T] \pmod{10^9 + 7}\] trong đó $T \subseteq S$ nghĩa là $(T \mathbin{\&} S) = T$ và $S \setminus T = S \oplus T$.
Để tránh phải in ra quá nhiều số, hãy tính và in ra giá trị: \[\sum_{S = 0}^{2^N - 1} (S + 1) \cdot H[S] \pmod{10^9 + 7}\]
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($0 \le N \le 18$).
- Dòng thứ hai chứa $2^N$ số nguyên $F[0], F[1], \dots, F[2^N - 1]$ ($0 \le F[i] < 10^9 + 7$).
- Dòng thứ ba chứa $2^N$ số nguyên $G[0], G[1], \dots, G[2^N - 1]$ ($0 \le G[i] < 10^9 + 7$).
Dữ liệu ra
- In ra một số nguyên duy nhất là kết quả bài toán.
Ví dụ
| Input | Output |
|---|---|
| 2 1 2 3 4 5 6 7 8 |
343 |
| 1 1 1 1 1 |
5 |
Giới hạn
- $0 \le N \le 18$
- $0 \le F[i], G[i] < 10^9 + 7$
Community Discussion