1. Идея

Нужно посчитать количество пар индексов (i, j), где i < j и c_i + c_j = X.

Перебирать все пары напрямую можно за O(n^2), но есть способ быстрее.

Будем идти по массиву слева направо и для каждой монеты c_i спрашивать:

• сколько монет с номиналом X - c_i уже встретилось раньше?

Каждая такая ранее встреченная монета образует с текущей подходящую пару.

Для этого удобно хранить в словаре количество уже встреченных значений.

2. Наблюдения

Наблюдение 1

Если текущая монета равна value, то ей нужна монета со значением need = X - value.

Если раньше уже встретилось k таких монет, то текущая монета добавляет ровно k новых пар.

Наблюдение 2

Важно считать только пары с i < j.

Если идти слева направо, то в словаре лежат только элементы с меньшими индексами. Значит, каждая пара будет учтена ровно один раз — в момент обработки правого элемента пары.

Наблюдение 3

Одинаковые значения обрабатываются естественно.

Например, если X = 6, а в массиве есть числа 3 3 3, то:

• первый 3 не образует пар;
• второй 3 образует 1 пару с первым;
• третий 3 образует 2 пары с предыдущими.

Итого получается 3 пары, что верно.

3. Алгоритм

1. Считываем n, X и массив монет.
2. Создаём словарь cnt, где cnt[v] — сколько раз значение v уже встретилось.
3. Создаём переменную answer = 0.
4. Для каждого элемента value массива:
   • вычисляем need = X - value;
   • добавляем к ответу cnt[need], если такое значение уже встречалось;
   • увеличиваем cnt[value] на 1.
5. Выводим answer.

4. Почему это работает

Докажем, что алгоритм считает ответ правильно.

Рассмотрим момент обработки элемента c_j.

• В словаре cnt уже хранятся количества всех элементов c_0, c_1, ..., c_{j-1}.
• Чтобы получить сумму X, нужен элемент c_i = X - c_j.
• Количество таких индексов i, где i < j, равно cnt[X - c_j].

Значит, при обработке c_j мы добавляем ровно число всех пар (i, j), заканчивающихся в j.

Так происходит для каждого j, поэтому:

• каждая подходящая пара будет учтена,
• ни одна пара не будет учтена дважды, потому что учитывается только при обработке второго элемента.

Следовательно, итоговое значение answer равно количеству всех пар (i, j), где i < j и c_i + c_j = X.

5. Сложность

Для каждого из n элементов выполняется фиксированное число операций со словарём.

• Время: O(n) в среднем.
• Память: O(n).

При n <= 5000 такое решение работает с большим запасом.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    long long X;
    cin >> n >> X;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<long long, long long> cnt;
    long long answer = 0;

    for (int i = 0; i < n; i++) {
        long long need = X - a[i];
        if (cnt.find(need) != cnt.end()) {
            answer += cnt[need];
        }
        cnt[a[i]]++;
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n, X = map(int, input().split())
a = list(map(int, input().split()))

cnt = {}
answer = 0

for value in a:
    need = X - value
    answer += cnt.get(need, 0)
    cnt[value] = cnt.get(value, 0) + 1

print(answer)