Пары шаблонов Язык Версия Время Память Все языки —...

Вот быстрое и нормальное решение на C++17.

Идея

У шаблона есть:

• mask — какие позиции фиксированы буквами
• code — какие именно там буквы

Два шаблона совместимы тогда и только тогда, когда
на всех позициях, где у обоих стоят буквы, буквы совпадают.

Так как m ≤ 6, всего масок максимум 2^6 = 64.
Сгруппируем все шаблоны по маске.

Как считать пары между двумя группами масок A и B

Пусть I = A & B — позиции, где оба шаблона имеют буквы.

Тогда шаблоны из этих групп совместимы только если их буквы на позициях I совпадают.

Значит:

• для группы B считаем, сколько шаблонов дают каждый возможный проектированный код на I
• для каждого шаблона из A смотрим, сколько в B имеют тот же проектированный код

Пары внутри одной группы

Если маска одна и та же, то совместимы только полностью одинаковые шаблоны.
То есть для каждого одинакового code добавляем cnt * (cnt - 1) / 2.

---

Код

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int MASKS = 1 << m;

    // freq[mask][code] = сколько раз встретился такой шаблон
    vector<unordered_map<int, int>> freq(MASKS);

    for (int k = 0; k < n; ++k) {
        string s;
        cin >> s;

        int mask = 0;
        int code = 0;

        for (int i = 0; i < m; ++i) {
            if (s[i] != '?') {
                mask |= (1 << i);
                code |= ((s[i] - 'a') << (5 * i)); // 5 бит хватает на 26 букв
            }
        }

        freq[mask][code]++;
    }

    // Удобнее и быстрее итерироваться по vector<pair<...>>
    vector<vector<pair<int, int>>> groups(MASKS);
    for (int mask = 0; mask < MASKS; ++mask) {
        groups[mask].reserve(freq[mask].size());
        for (auto &it : freq[mask]) {
            groups[mask].push_back(it);
        }
    }

    auto project = [&](int code, int interMask) -> int {
        // сжимаем буквы только на позициях interMask в компактный код
        int res = 0;
        int shift = 0;
        for (int i = 0; i < m; ++i) {
            if (interMask & (1 << i)) {
                int letter = (code >> (5 * i)) & 31;
                res |= (letter << shift);
                shift += 5;
            }
        }
        return res;
    };

    long long ans = 0;

    for (int A = 0; A < MASKS; ++A) {
        // пары внутри одной группы:
        // совместимы только полностью одинаковые шаблоны
        for (auto &[code, cnt] : groups[A]) {
            ans += 1LL * cnt * (cnt - 1) / 2;
        }

        // пары между разными группами
        for (int B = A + 1; B < MASKS; ++B) {
            int I = A & B;

            unordered_map<int, int> cntB;
            cntB.reserve(groups[B].size() * 2 + 1);

            for (auto &[code, cnt] : groups[B]) {
                cntB[project(code, I)] += cnt;
            }

            for (auto &[code, cnt] : groups[A]) {
                auto it = cntB.find(project(code, I));
                if (it != cntB.end()) {
                    ans += 1LL * cnt * it->second;
                }
            }
        }
    }

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

---

Почему работает

Для двух шаблонов важно только одно:

• если в какой-то позиции у обоих буквы разные — общего слова нет
• иначе общее слово существует

Если маски фиксированных позиций равны A и B, то проверять надо только пересечение A & B.
На остальных позициях один из шаблонов имеет ?, значит конфликта быть не может.

---

Сложность

• масок всего ≤ 64
• шаблонов ≤ 50000

Итоговая сложность примерно: O(64² · K · m), где K — среднее число различных шаблонов в группе.
При m ≤ 6 это спокойно проходит.

Если хочешь, я могу ещё сразу скинуть более короткую версию без комментариев, чисто для сдачи.