Зустріч посередині#11431

Зустріч посередині (Розбір)

Розіб'ємо вхідний масив на дві рівні частини: $t_{1}, t_{2}, ..., t_{n /2}$ t_1, t_2, ..., t_{n/2} і $t_{n /2 + 1}, t_{n /2 + 2}, ..., t_{n}$ t_{n/2+1}, t_{n/2+2}, ..., t_n. Першу частину збережемо в масиві $a$ , другу — в масиві $b$ .

Спочатку вирішимо задачу для послідовності $a$ . Переберемо всі її можливі підмножини (їх буде не більше $2^{20}$ 2^{20}). Для кожної підмножини обчислимо суму її елементів $s$ , і для кожної такої суми збільшимо значення $m [s]$ на $1$ . Як структуру даних $m$ можна використовувати, наприклад, unordered_map. Таким чином, $m [s]$ буде містити кількість способів вибрати підмножину з масиву $a$ з сумою елементів, рівною $s$ .

Потім переберемо всі підмножини масиву $b$ . Нехай $s u m$ — сума елементів однієї з таких підмножин. Якщо об'єднати цю підмножину з усіма підмножинами масиву $a$ , сума елементів яких дорівнює $s - s u m$ s - sum, то в результаті вийде підмножина вхідного масиву, сума елементів якої дорівнює $s$ .

Приклад

Розглянемо другий приклад. Розіб'ємо вхідну послідовність на дві частини:

$a = (1, 3, 2)$ a = (1, 3, 2),
$b = (2, 1, 4)$ b = (2 ,1, 4)

Переберемо всі підмножини множини $a = {1, 3, 2}$ a = \{1, 3, 2\}:

${1} : s u m = 1, m [1] + +$ \{1\}: sum = 1, m[1]++;	${1, 2} : s u m = 3, m [3] + +$ \{1, 2\}: sum = 3, m[3]++;
${3} : s u m = 3, m [3] + +$ \{3\}: sum = 3, m[3]++;	${3, 2} : s u m = 5, m [5] + +$ \{3, 2\}: sum = 5, m[5]++;
${2} : s u m = 2, m [2] + +$ \{2\}: sum = 2, m[2]++;	${1, 3, 2} : s u m = 6, m [6] + +$ \{1, 3, 2\}: sum = 6, m[6]++;
${1, 3} : s u m = 4, m [4] + +$ \{1, 3\}: sum = 4, m[4]++;	${} : s u m = 0, m [0] + +$ \{\}: sum = 0, m[0]++;

Структура $m$ після обробки буде містити наступні значення:

Тепер переберемо всі підмножини множини $b = {2, 1, 4}$ b = \{2, 1, 4\}. У даному прикладі шуканою сумою є $s = 7$ s = 7. Для кожної суми $s u m$ , що відповідає підмножині $b$ , будемо додавати до відповіді значення $m [s - s u m] .$ m[s - sum].

${2} : s u m = 2, m [7 - 2] = m [5] = 1$ \{2\}: sum = 2, m[7 - 2] = m[5] = 1;
${1} : s u m = 1, m [7 - 1] = m [6] = 1$ \{1\}: sum = 1, m[7 - 1] = m[6] = 1;
${4} : s u m = 4, m [7 - 4] = m [3] = 2$ \{4\}: sum = 4, m[7 - 4] = m[3] = 2;
${2, 1} : s u m = 3, m [7 - 3] = m [4] = 1$ \{2, 1\}: sum = 3, m[7 - 3] = m[4] = 1;
${2, 4} : s u m = 6, m [7 - 6] = m [1] = 1$ \{2, 4\}: sum = 6, m[7 - 6] = m[1] = 1;
${1, 4} : s u m = 5, m [7 - 5] = m [2] = 1$ \{1, 4\}: sum = 5, m[7 - 5] = m[2] = 1;
${2, 1, 4} : s u m = 7, m [7 - 7] = m [0] = 1$ \{2, 1, 4\}: sum = 7, m[7 - 7] = m[0] = 1;
${} : s u m = 0, m [7 - 0] = m [7] = 0$ \{\}: sum = 0, m[7 - 0] = m[7] = 0;

Шукана сума дорівнює $1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8$ 1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8, що і є відповіддю.

Реалізація алгоритму

Оголосимо робочі структури даних.

vector<int> a, b;
unordered_map<long long, long long> m;

Читаємо вхідні дані. Першу половину послідовності заносимо в масив $a$ , другу — в масив $b$ .

scanf("%d %d", &n, &s);
a.resize(n / 2);
for (i = 0; i < n / 2; i++)
  scanf("%d", &a[i]);

b.resize(n - n / 2);
for (i = n / 2; i < n; i++)
  scanf("%d", &b[i - n / 2]);

C++

Перебираємо всі підмножини послідовності $a$ і обчислюємо суми їхніх елементів. У структурі unordered_map зберігаємо, скільки разів кожна сума зустрічається серед цих підмножин. Якщо $s u m$ — сума поточної підмножини, то значення $m [s u m]$ збільшуємо на $1$ .

for (i = 0; i < (1 << a.size()); i++)
{
  sum = 0;

Змінна $i$ містить бітову маску поточної підмножини $а$ . Сума її елементів обчислюється у змінній $s u m$ .

      for (j = 0; j < a.size(); j++)
        if (i & (1 << j)) sum += a[j];

Для кожної знайденої суми sum збільшуємо значення $m [s u m]$ на $1$ .

  m[sum]++;
}

Кількість способів отримати суму $s$ з елементів вихідного масиву підраховуємо у змінній $r es$ .

res = 0;

Перебираємо всі підмножини послідовності $b$ .

for (i = 0; i < (1 << b.size()); i++)
{
  sum = 0;

Змінна $i$ містить бітову маску поточної підмножини $b$ . Сума елементів цієї підмножини обчислюється у змінній $s u m$ .

  for (j = 0; j < b.size(); j++)
    if (i & (1 << j)) sum += b[j];

Якщо об'єднати поточну підмножину множини $b$ , сума елементів якої дорівнює $s u m$ , з усіма підмножинами множини $a$ , сума яких дорівнює $s - s u m$ s - sum, то в результаті вийде підмножина вхідного масиву, сума елементів якої дорівнює $s$ .

  if (m.count(s - sum) > 0) res += m[s - sum];
}

Виводимо відповідь.

printf("%lld\n", res);