Tích chập tập con

Buổi 33 — Bitmask DP & SOS DP
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved