62302023-11-08 12:06:03Error42Forgó rulettkerékcpp17Elfogadva 100/100890ms98624 KiB
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

using ll = long long;

template <ll M>
struct modular {
    ll val;

    // n >= 0
    modular(const ll n) {
        if (n < M)
            val = n;
        else if (n < 2 * M)
            val = n - M;
        else
            val = n % M;
    }

    [[nodiscard]] modular operator +(const modular& rhs) const {
        return val + rhs.val;
    }

    [[nodiscard]] modular operator -(const modular& rhs) const {
        return val + M - rhs.val;
    }

    [[nodiscard]] modular operator *(const modular& rhs) const {
        return val * rhs.val;
    }

    // p >= 0
    [[nodiscard]] modular pow(const ll& p) const {
        if (p == 0)
            return 1;

        if (p % 2 == 0)
            return (*this * *this).pow(p / 2);
        else
            return *this * pow(p - 1);
    }

    [[nodiscard]] modular inv() const {
        return pow(M - 2);
    }

    [[nodiscard]] modular operator /(const modular& rhs) const {
        return *this * rhs.inv();
    }

    modular& operator +=(const modular& rhs) {
        return *this = *this + rhs;
    }

    modular& operator -=(const modular& rhs) {
        return *this = *this - rhs;
    }

    modular& operator *=(const modular& rhs) {
        return *this = *this * rhs;
    }

    modular& operator /=(const modular& rhs) {
        return *this = *this / rhs;
    }

    explicit operator ll() const {
        return val;
    }
};

template <ll M>
ostream& operator<<(ostream& os, const modular<M>& modular) {
    cout << modular.val;
    return os;
}

using mod = modular<ll(1e14) + 39>;

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

    ll n, m;
    cin >> n >> m;

    mod fp = 1;
    for (int i = 0; i < m - 1; i++)
        fp *= 31;

    map<ll, ll> hashes;
    ll ans = 0;

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

        mod cur_hash = 0;

        for (char const& c : s) {
            cur_hash *= 31;
            cur_hash += c - 'a' + 1;
        }

        ans += hashes[ll(cur_hash)];

        set<ll> cur_hashes;
        cur_hashes.insert(ll(cur_hash));

        for (int i = 0; i < m - 1; i++) {
            cur_hash -= fp * (s[i] - 'a' + 1);
            cur_hash *= 31;
            cur_hash += (s[i] - 'a' + 1);

            cur_hashes.insert(ll(cur_hash));
        }

        for (ll const h : cur_hashes)
            hashes[ll(h)]++;
    }

    cout << ans << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Elfogadva3ms2188 KiB
subtask220/20
3Elfogadva3ms2428 KiB
4Elfogadva3ms2428 KiB
5Elfogadva3ms2628 KiB
6Elfogadva6ms2860 KiB
7Elfogadva7ms4060 KiB
8Elfogadva6ms3176 KiB
9Elfogadva6ms3348 KiB
subtask315/15
10Elfogadva98ms5120 KiB
11Elfogadva119ms7332 KiB
12Elfogadva149ms12792 KiB
13Elfogadva101ms7208 KiB
14Elfogadva108ms8024 KiB
15Elfogadva250ms37512 KiB
16Elfogadva305ms48804 KiB
17Elfogadva268ms42692 KiB
subtask465/65
18Elfogadva356ms15460 KiB
19Elfogadva351ms10064 KiB
20Elfogadva695ms59984 KiB
21Elfogadva732ms53968 KiB
22Elfogadva479ms31748 KiB
23Elfogadva365ms10680 KiB
24Elfogadva633ms47204 KiB
25Elfogadva523ms25800 KiB
26Elfogadva216ms5464 KiB
27Elfogadva527ms32404 KiB
28Elfogadva890ms98624 KiB
29Elfogadva168ms11276 KiB
30Elfogadva523ms47596 KiB