გეომეტრიული პროგრესია



პოლიკარტეს ძალიან უყვარს გეომეტრიული პროგრესიები. იგი მხოლოდ 3 წლისაა, ამიტომაც ისეთი გეომეტრიული პროგრესიები უყვარს, რომელთა სიგრძეც სამია. მას ასევე აქვს საყვარელი მთელი რიცხვი K და N ცალი რიცხვისაგან შემდგარი მიმდევრობა A.

პოლიკარტეს აინტერესებს, რამდენი 3 სიგრძის ქვემიმდევრობის ამორჩევაა შესაძლებელი A-დან, ისე რომ ის გეომეტრიულ პროგრესიას ადგენდეს მნიშვნელით K.

3 სიგრძის ქვემიმდევრობა არის 3 ინდექსის i1, i2, i3 ისეთი კომბინაცია რომ 1 ≤  i1 < i2 < i3≤ N.
სხვა სიტყვებით რომ ვთქვათ, 3 სიგრძის ქვემიმდევრობა არის სამი ელემენტისგან შემდგარი ისეთი ჯგუფი, რომელშიც ელემენტები აუცილებლად თანმიმდევრობით არაა დალაგებული, მაგრამ მათი ინდექსები მკაცრად ზრდადია.

გეომეტრიული პროგრესია მნიშვნელით K არის რიცხვების ისეთი მიმდევრობა, რომელსაც აქვს შემდეგი ფორმა: b · k0, b · k1, ... , b · k r – 1.

პოლიკარტე მხოლოდ 3 წლისაა, შესაბამისად, მას არ შეუძლია ამ რიცხვის დათვლა. დაეხმარე მას ამის გაკეთებაში.

შემავალი მონაცემები:
შემავალი მონაცემების პირველი ხაზი წარმოადგენს ორ მთელ რიცხვს, N და K (1 ≤ n, k ≤ 2·105), რომლებიც უჩვენებენ თუ რამდენი რიცხვია პოლიკარტეს მიმდევრობაში და მის საყვარელ მთელ რიცხვს.
მეორე ხაზი კი N ცალი მთელი რიცხვია a1, a2, ... , an ( - 109 ≤ ai ≤ 109) – მიმდევრობის ელემენტები.


გამომავალი მონაცემები:
გამომავალი მონაცემი უნდა იყოს ერთი რიცხვი – რამდენნაირი 3 სიგრძის ქვემიმდევრობის არჩევაა შესაძლებელი, ისე რომ გეომეტრიულ პროგრესიას ადგენდეს მნიშვნელით K.

 

 

მაგალითები

შემავალი მონაცემები

5 2
1 1 2 2 4

გამომავალი მონაცემები

4

 

 

შემავალი მონაცემები

3 1
1 1 1

გამომავალი მონაცემები

1

 

 

შემავალი მონაცემები

10 3
1 2 6 2 3 6 9 18 3 9

გამომავალი მონაცემები

6

 

 

შენიშვნა

პირველ მაგალითში პასუხი არის 4, რადგან ქვემიმდევრობის პირველ ელემენტად ნებისმიერი 1-იანის არჩევა შეიძლება, მეორე ელემენტად ნებისმიერი 2-იანის და მესამე ელემენტი კი აუცილებლად 4 უნდა იყოს.

 

 


 

ამოცანის ამოსახსნელად განვიხილოთ პროგრესიის შუა ელემენტი. ეს ნიშნავს, რომ თუ დავაფიქსირებთ ai ელემენტს, მაშინ პროგრესია უნდა შედგებოდეს ai / K და ai · K ელემენტებისგან. ასე ვერ მოხდება, თუ თავად ai არ იყოფა K-ზე (ai mod K 0).

 

დაფიქსირებული შუა ელემენტისათვის შეგვიძლია ვიპოვოთ მიმდევრობათა რაოდენობა შემდეგნაირად: დავთვალოთ რამდენი ai / K ელემენტია მის მარცხნივ და რამდენი ai · K ელემენტია მის მარჯვნივ. ამ რაოდენობათა ნამრავლი იქნება ამოცანის პასუხი.

 

მაგალითის დეტალური განხილვა

შემომავალი მონაცემები შევინახოთ მასივში.

გამოვყოთ პასუხისათვით განკუთვნილი ცვლადი answer, რომელიც შეინახავს სასურველი გეომეტრიული პროგრესიების რაოდენობას.

 

answer = 0

 

1

1

2

2

4

 

დამატებით შემოვიღოთ 2 Map (ასახვა) სტრუქტურა, რომელთა გასაღები (Key) იქნება შემომავალი მონაცემი, მნიშვნელობა (Value) კი - სიხშირე (რამდენჯერ გვხვდება იგი). თითოეული მომენტისათვის უნდა ვიცოდეთ მონაცემთა სიხშირე ყოველი დაფიქსირებული კურსორის მარცხნივ და მარჯვნივ. 2 Map სწორედ ამისთვის გვჭირდება.

 

მონაცემთა განხილვას ვიწყებთ მარცხნიდან მარჯვნივ, შესაბამისად, თავდაპირველად გვექნება ასეთი მდგომარეობა:

 

numsLeft = {}

numsRight = {1 : 2, 2 : 2, 4 : 1}

answer = 0

 

numsLeft

მნიშვნელობა

სიხშირე

 

numsRight

მნიშვნელობა

სიხშირე

1

2

2

2

4

1

 

დავიწყოთ მონაცემთა განხილვა.

 

1

1

2

2

4

1-იანი არ იყოფა 2-ზე, ეს რიცხვი ვერ იქნება სასურველი გეომეტრიული პროგრესიის შუა წევრი, ამიტომაც მხოლოდ სიხშირეები განვაახლოთ.

 

NumsLeft = {1 : 1}

numsRight = {1 : 1, 2 : 2, 4 : 1}

 

answer = 0

 

numsLeft

მნიშვნელობა

სიხშირე

1

1

 

 

numsRight

მნიშვნელობა

სიხშირე

1

1

2

2

4

1

 

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

აქაც ანალოგიური შემთხვევა გვაქს, შევასრულოთ იგივე.

 

 

NumsLeft = {1 : 2}

numsRight = {2 : 2, 4 : 1}

 

 

answer = 0

 

numsLeft

მნიშვნელობა

სიხშირე

1

2

 

 

numsRight

მნიშვნელობა

სიხშირე

2

2

4

1

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

 

2-იანი იყოფა 2-ზე, ამიტომ “მარცხენა” Map-ში ვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [1, 2, 4]) მარცხენა კიდურა წევრი იქნება.

 

მოვნახოთ 1-იანის სიხშირე და დავიმახსოვროთ.

NumsLeft[1] = 2

 

ახლა კი “მარჯვენა” Map-ში ვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [1, 2, 4]) მარჯვენა კიდურა წევრი იქნება.

 

მოვნახოთ 4-იანის სიხშირე და დავიმახსოვროთ.

NumsRight[4] = 1

 

ახლა კი answer ცვლადს დავუმატოთ დამახსოვრებულ მნიშვნელობათა ნამრავლი და განვაახლოთ სიხშირეები:

answer += 1 * 2

 

NumsLeft = {1 : 2, 2 : 1}

numsRight = {2 : 1, 4 : 1}

 

 

answer = 2

 

numsLeft

მნიშვნელობა

სიხშირე

1

2

2

1

 

numsRight

მნიშვნელობა

სიხშირე

2

1

4

1

 

 

გადავიდეთ შემდეგ მონაცემზე.

 

1

1

2

2

4

 

აქაც წინა სიტუაციის ანალოგიური მდგომარეობა გვაქვს.

 

NumsLeft[1] = 2

numsRight[4] = 1

 

answer += 1 * 2

 

განვაახლოთ სიხშირეები.

 

NumsLeft = {1 : 2, 2 : 2}

numsRight = {4 : 1}

 

 

answer = 4

 

numsLeft

მნიშვნელობა

სიხშირე

1

2

2

2

 

numsRight

მნიშვნელობა

სიხშირე

4

1

 

გადავიდეთ ბოლო მონაცემზე.

 

1

1

2

2

4

 

 

4-იანი იყოფა 2-ზე, ამიტომ “მარცხენა” Map-ში მოვნახოთ რამდენი ისეთი წევრი გვაქვს, რომელიც სასურველი გეომეტრიული პროგრესიის (ამ შემთხვევაში [2, 4, 8]) მარცხენა კიდურა წევრი იქნება.

 

NumsLeft[2] = 2

 

ახლა კი “მარჯვენა” Map-ში უნდა მოვნახოთ პროგრესიის მარჯვენა კიდურა წევრის სიხშირე, მაგრამ ცხადია ასეთი არ მოიძებნება.

 

NumsRight[8] = 0

 

answer ცვლადი განახლებისას არ შეიცვლება.

 

Answer += 0 * 2

 

განვაახლოთ სიხშირეები.

 

NumsLeft = {1 : 2, 2 : 2, 4 : 1}

numsRight = {}

 

 

answer = 4

 

numsLeft

მნიშვნელობა

სიხშირე

1

2

2

2

4

1

 

numsRight

მნიშვნელობა

სიხშირე

ყველა მონაცემის გადარჩევის შემდეგ დავბეჭდოთ answer ცვლადი.

 

ამოხსნის კოდი

#include <iostream>
#include <map>
using namespace std;

void SubsequencesOfLengthThree() {
  map <long long, long long> numsLeft;
  map <long long, long long> numsRight;
  long long N;
  long long K;
  long long sequence[300010];
  long long ans;

  scanf("%lld %lld", &N, &K);

  for (int i = 0; i < N; i++) {
      scanf("%lld", &sequence[i]);
      numsRight[sequence[i]]++;
  }

  for (int i = 0; i < N; i++) {
      long long elementsLeft = 0;
      long long elementsRight = 0;

      if (sequence[i] % K == 0) {
          elementsLeft = numsLeft[sequence[i] / K];
      }

      numsRight[sequence[i]]--;
      elementsRight = numsRight[sequence[i] * K];
      ans += elementsLeft * elementsRight;
      numsLeft[sequence[i]]++;
  }

  printf("%lldn", ans);
}

int main() {
  SubsequencesOfLengthThree();

  return 0;
}