Авiашляхи Потоколяндiї#314

Автор: Єгор Дубовік

Розробник: Ігор Баренблат

Визначимо $a \subset b$ a \subset b — вираз, що означає, що $a$ $an d$ $b = a$ b=a ( $a$ є «підмаскою» $b$ ). Тут $an d$ — побітове І.

Розв'язуватимемо задачу покроково.

Визначимо $D_{i}$ D_i — $m$ -бітова маска, де $j$ -ий біт рівний $1$ , якщо місто з номером $i$ належить списку з номером $j$ , та $0$ в протилежному випадку.
Як порахувати $D$ ? Це домашнє завдання :)
Визначимо $c n t D_{i}$ cntD_i — кількість таких $j$ , що $D_{j} = i$ D_j = i.
Як порахувати $c n t D$ ? Це домашнє завдання :)
Визначимо $in t er sec t_{ma s k}$ intersect_{mask} — кількість авіашляхів, що можуть утворитися за використання будь-якого зі списків, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ .
Як порахувати $in t er sec t$ ? $in t er sec t_{ma s k} =$ intersect_{mask}= $(2 s u m _{ma s k \subset a} c n t D _{a})$ {sum_{mask \subset a} cntD_a}\choose{2} (Для того щоб швидко порахувати значення, використовуйте ідею super magic algo(описано нижче)).
Визначимо $u ni o n_{ma s k}$ union_{mask} — кількість авіашляхів, що будуть утворені за використання списків, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ (помітимо, що це значення не залежить від порядку використання списків).
Як порахувати $u ni o n$ ? Посилаючись на формулу включень-виключень, отримуємо: $u ni o n_{ma s k} = s u m_{a \subset ma s k} ((- 1)^{bi t s (a) + 1} \cdot in t er sec t_{a})$ union_{mask}=sum_{a\subset mask} ((-1)^{bits(a)+1}\cdot intersect_a) (Для того щоб швидко порахувати значення, використовуйте super magic algo(описано нижче)). Тут $bi t s (m)$ — кількість одиничних бітів маски $m$ .
Розв'язуватимемо задачу методом динамічного програмування. Визначимо $d p_{ma s k}$ dp_{mask} — максимальна кількість грошових одиниць, які можна заробити, використавши списки, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ у довільному порядку.
Як порахувати $d p$ ? $d p_{0} = 0$ dp_0=0. $d p_{ma s k} = max (d p_{ma s k}$ dp_{mask}=\max (dp_{mask} $_{x or}$ _{xor} $_{2^{i}} + f (u ni o n_{ma s k} - u ni o n_{ma s k}$ _{2^i} + f(union_{mask}-union_{mask} $_{x or}$ _{xor} $_{2^{i}}) \cdot r_{i})$ _{2^i}) \cdot r_i), де $i$ — номери одиничних бітів $m$ -бітової маски $ma s k$ . Тут $x or$ — побітове виключне АБО.
Відповіддю до задачі є $d p_{2^{m} - 1}$ dp_{2^{m}-1}.

/// super magic algo

Нехай задається масив $a$ розміру $2^{m}$ 2^m. Необхідно знайти значення масиву $b$ , де $b_{i} = s u m_{j \subset i} a_{j}$ b_i=sum_{j \subset i} a_j.

Здійснимо $m$ ітерацій, де після ітерації з номером $i$ значенням $b [x]$ буде $\sum a [y]$ \sum_{}a[y], таких що $x$ $an d$ $y = y$ y = y, та починаючи з біта з номером $i$ біти чисел $x$ та $y$ збігаються (біти нумеруються з 0).

Очевидно, що перед першою ітерацією $b [x] = a [x]$ b[x]=a[x]. На ітерації з номером $i$ перерахуємо $b [x]$ .

Якщо в числі x біт з номером $i$ рівний $0$ , то $b_{n e w} [x] = b [x]$ b_{new}[x]=b[x].

Якщо в числі x біт з номером $i$ рівний $1$ , то $b_{n e w} [x] = b [x] + b [x$ b_{new}[x]=b[x]+b[x $x or$ $2^{i}]$ 2^i].

Отже, легко реалізувати цей алгоритм так:

for (int i=0;i<(1<<m);i++){
    b[i]=a[i];
}
for (int i=0;i<m;i++){
    for (int mask=0;mask<(1<<m);mask++){
        if (mask&(1<<i)){
            b[mask]+=b[mask^(1<<i)];
        }
    }
}

/// end of super magic algo

Складність $O (n \cdot m + m \cdot 2^{m})$ O(n\cdot m+m\cdot 2^m) часу та $O (n + 2^{m})$ O(n+2^m) пам'яті.