I. Суммы по надмаскам

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

Как классная задача I, но суммировать надо по надмаскам: посчитайте

Q[i] = \sum_{j \supseteq i} F[j],

то есть по всем маскам $j$ , у которых единичных битов не меньше, чем у $i$ , и все биты $i$ входят в $j$ .

Первая строка содержит число $n$ ( $1 \le n \le 20$ ).

Вторая строка — $2^n$ чисел $F[i]$ ( $|F[i]| \le 10^9$ ).

Одна строка из $2^n$ чисел.

ввод

2
1 2 3 4

вывод

10 6 7 4

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

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