企鹅 QQ(Penguin QQ) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

using ull = unsigned long long;
const ull B1 = 131;
const ull B2 = 13331;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, L, S;
    if (!(cin >> n >> L >> S)) return 0;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<vector<ull>> pre(n, vector<ull>(L + 1, 0)), suf(n, vector<ull>(L + 2, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= L; ++j) {
            pre[i][j] = pre[i][j - 1] * B1 + (ull)a[i][j - 1];
        }
        for (int j = L; j >= 1; --j) {
            suf[i][j] = suf[i][j + 1] * B2 + (ull)a[i][j - 1];
        }
    }

    long long ans = 0;
    vector<ull> h(n);
    for (int pos = 1; pos <= L; ++pos) {
        for (int i = 0; i < n; ++i) {
            h[i] = pre[i][pos - 1] * 1000000007ULL + suf[i][pos + 1];
        }
        sort(h.begin(), h.end());
        long long run = 1;
        for (int i = 1; i < n; ++i) {
            if (h[i] == h[i - 1]) {
                ans += run;
                ++run;
            } else {
                run = 1;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}