ABA#9594

ABA (Həll təhlili)

Güman edək ki, $s_{0} s_{1} ... s_{n - 1}$ s_0s_1...s_{n-1} girişi verilir. Tutaq ki, $l [i]$ $0$ -cı mövqedən $i$ -ci mövqeyə qədər olan $A$ hərflərinin sayını saxlayır. $c n t$ isə sözün daxilindəki $A$ hərflərinin ümumi sayıdır. O zaman, $i$ -dən sonra $c n t - l [i]$ cnt - l[i] sayda $A$ hərfi var.

Əgər $B$ hərfi $i$ -ci mövqedədirsə, o zaman $B$ -nin solunda $l [i]$ sayda $A$ və sağında $(c n t - l [i])$ (cnt - l[i]) sayda $A$ hərfi var. $B$ hərfinin $i$ -ci mövqedə olduğu $" A B A "$ alt-ardıcıllıqlarının sayı $l [i] \cdot (c n t - l [i])$ l[i] \cdot (cnt - l[i])-yə bərabərdir.

Qalır $" A B A "$ alt-ardıcıllıqlarının sayını $B$ hərfinin olduğu mövqelər üçün ümumiləşdirmək.

İkinci həll. Sətiri soldan sağa doğru keçərək $A$ hərflərinin sayını $a$ dəyişənində saxlayacağıq.

Hər $B$ hərfi üçün $A$ ilə bitən $a$ qədər $A B$ alt-ardıcıllığı var (hazırda $B$ -dən əvvəl tam olaraq $a$ qədər $A$ var). $ab$ dəyişənində $A B$ alt-ardıcıllıqlarının sayını saxlayacağıq. Hər $B$ hərfinə görə $ab$ -a $a$ əlavə edilməlidir.

Hər bir $A$ hərfi üçün artıq mövcud olan $ab$ qədər $A B$ ilə başa çatan alt-ardıcıllıqlar var. $aba$ dəyişənində $A B A$ alt-ardıcıllıqlarının ümumi sayını saxlayacağıq. Hər $A$ hərfi üçün $aba$ -ya $ab$ əlavə edilməlidir.

Misal

İkinci misalın üzərindən keçək.

"ABA" alt-ardıcıllıqlarının sayı

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

Gəlin problemə ikinci üsulla həll edərkən dəyişənlərin dəyərlərinə nəzər salaq.

Alqoritmin realizasiyası

Giriş sətiri $s$ oxuyuruq.

cin >> s;

Dəyişənlərimizi ilkinləşdiririk.

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

Hər bir $i$ mövqedə $l [i]$ -ə $0$ -cı mövqedən $i$ -ci mövqeyə qədər olan $A$ hərflərin sayını daxil edirik. Dövr bitdikdən sonra $c n t$ -də $A$ hərflərin ümumi sayı qalır.

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

Nəticəni $r es$ dəyişənində saxlayırıq.

res = 0;

$B$ hərfinin olduğu hər bir $i$ mövqedə $" A B A "$ alt-ardıcıllıqlarının sayını hesablayırıq.

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

Nəticəni çap edirik.

cout << res;

Alqoritmin realizasiyası — kombinasiyalı sayma

Giriş sətiri $s$ oxuyuruq.

cin >> s;

Dəyişənlərimizi ilkinləşdiririk.

a = ab = aba = 0;

Sətirin hər bir simvolunu yoxlayırıq. Dəyişənlər $a, ab$ və $aba$ -nın dəyərini yeniləyirik.

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

C++

Nəticəni çap edirik.

cout << aba << endl;

Python realizasiyası

Giriş sətiri $s$ oxuyuruq.

s = input()

Dəyişənlərimizi ilkinləşdiririk.

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

Hər bir $i$ mövqedə $l [i]$ -ə $0$ -cı mövqedən $i$ -ci mövqeyə qədər olan $A$ hərflərin sayını daxil edirik. Dövr bitdikdən sonra $c n t$ -də $A$ hərflərin ümumi sayı qalır.

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

Nəticəni $r es$ dəyişənində saxlayırıq.

res = 0

$B$ hərfinin olduğu hər bir $i$ mövqedə $" A B A "$ alt-ardıcıllıqlarının sayını hesablayırıq.

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

Nəticəni çap edirik.

print(res)

Python realizasiyası — kombinasiyalı sayma

Giriş sətiri $s$ oxuyuruq.

s = input()

Dəyişənlərimizi ilkinləşdiririk.

a = ab = aba = 0

Sətirin hər bir simvolunu yoxlayırıq. Dəyişənlər $a, ab$ və $aba$ -nın dəyərini yeniləyirik.

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

Nəticəni çap edirik.

print(aba)