ABA#9594

ABA (Розбір)

Нехай $s_{0} s_{1} ... s_{n - 1}$ s_0s_1...s_{n-1} — вхідний рядок. Нехай $l [i]$ містить кількість літер $А$ з позиції $0$ до $i$ -ї включно. Нехай $c n t$ дорівнює загальній кількості літер $А$ у слові. Тоді справа від позиції $i$ знаходиться $c n t - l [i]$ cnt - l[i] літер $А$ .

Якщо літера $B$ знаходиться у $i$ -й позиції, то зліва від неї знаходиться $l [i]$ літер $А$ , а справа $(c n t - l [i])$ (cnt - l[i]) літер $А$ . Кількість підпослідовностей " $A B A$ ", де літера $B$ знаходиться у $i$ -й позиції, дорівнює $l [i] \cdot (c n t - l [i])$ l[i] \cdot (cnt - l[i]).

Залишається просумувати значення $l [i] \cdot (c n t - l [i])$ l[i] \cdot (cnt - l[i]) по всіх позиціях $i$ , де знаходиться літера $B$ .

Друге рішення. Підемо по рядку зліва направо і будемо в змінній $a$ підраховувати кількість літер $A$ .

Для кожної літери $B$ в рядку у нас утворюється $a$ слів $A B$ (перед поточною літерою $B$ є рівно $a$ літер $A$ ). У змінній $ab$ будемо підраховувати кількість слів $A B$ , які зустрілися. Для кожної літери $B$ до $ab$ слід додати $a$ .

Для кожної поточної літери $A$ перед нею є $ab$ слів $A B$ . У змінній $aba$ підраховуємо кількість слів $A B A$ , які зустрілися. Для кожної літери $A$ до $aba$ слід додати $а b$ .

Приклад

Розглянемо другий тест.

Кількість підпослідовностей " $A B A$ " дорівнює

1 \cdot 5 + 2 \cdot 4 + 2 \cdot 4 + 2 \cdot 4 = 5 + 8 + 8 + 8 = 29

1 \cdot 5 + 2 \cdot 4 + 2 \cdot 4 + 2 \cdot 4 = 5 + 8 + 8 + 8 = 29

Розглянемо значення змінних у разі розв'язання задачі другим способом.

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

Читаємо вхідний рядок $s$ .

cin >> s;

Ініціалізуємо змінні.

cnt = 0; len = s.size();
l.resize(len);

Для кожної позиції $i$ занесемо в $l [i]$ кількість літер $А$ з позиції $0$ до $i$ -ї включно. Після закінчення циклу змінна $c n t$ міститиме загальну кількість літер $А$ .

for (i = 0; i < len; i++)
{
  if (s[i] == 'A') cnt++;
  l[i] = cnt;
}

У змінній $r es$ підраховуємо відповідь.

res = 0;

Для кожної позиції $i$ , де знаходиться літера $В$ , підраховуємо кількість підпослідовностей " $A B A$ ".

for (i = 0; i < len; i++)
  if (s[i] == 'B') res += 1LL * l[i] * (cnt - l[i]);

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

cout << res;

Реалізація алгоритму — комбінаторний підрахунок

Читаємо вхідний рядок $s$ .

cin >> s;

Ініціалізуємо змінні.

a = ab = aba = 0;

Перебиратимемо символи рядка. Перераховуємо змінні $a, ab$ і $aba$ .

for (i = 0; i < s.size(); i++) 
  if (s[i] == 'A')
  {
    a++;
    aba += ab;
  }
  else
  if (s[i] == 'B') ab += a;

C++

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

cout << aba << endl;

Python реалізація

Читаємо вхідний рядок $s$ .

s = input()

Ініціалізуємо змінні.

cnt = 0
n = len(s)
l = [0] * n

for i in range(n):
  if s[i] == 'A':
    cnt += 1
  l[i] = cnt

У змінній $r es$ підраховуємо відповідь.

res = 0

Для кожної позиції $i$ , де знаходиться літера $В$ , підраховуємо кількість підпослідовностей " $A B A$ ".

for i in range(n):
  if s[i] == 'B':
    res += l[i] * (cnt - l[i])

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

print(res)

Python реалізація — комбінаторний підрахунок

Читаємо вхідний рядок $s$ .

s = input()

Ініціалізуємо змінні.

a = ab = aba = 0

Перебиратимемо символи рядка. Перераховуємо змінні $a, ab$ і $aba$ .

for c in s:
  if c == 'A':
    a += 1
    aba += ab
  if c == 'B':
    ab += a

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

print(aba)