H. Суммы по подмножествам

2500 мс · 256 МБ · всё или ничего

Дан массив $a$ длины $2^n$ , занумерованный масками. Для каждой маски посчитайте

f[\text{mask}] = \sum_{\text{sub} \subseteq \text{mask}} a[\text{sub}],

и выведите сумму всех $f[\text{mask}]$ по модулю $10^9 + 7$ .

В первой строке $n$ ( $1 \le n \le 18$ ). Во второй — $2^n$ чисел $a_i$ ( $0 \le a_i \le 10^9$ ), занумерованных от 0 до $2^n - 1$ .

Выведите сумму всех $f[\text{mask}]$ по модулю $10^9 + 7$ .

ввод

1
1 2

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.