6230 2023. 11. 08 12:06:03 Error42 Forgó rulettkerék cpp17 Elfogadva 100/100 890ms 98624 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 3ms 2188 KiB
subtask2 20/20
3 Elfogadva 3ms 2428 KiB
4 Elfogadva 3ms 2428 KiB
5 Elfogadva 3ms 2628 KiB
6 Elfogadva 6ms 2860 KiB
7 Elfogadva 7ms 4060 KiB
8 Elfogadva 6ms 3176 KiB
9 Elfogadva 6ms 3348 KiB
subtask3 15/15
10 Elfogadva 98ms 5120 KiB
11 Elfogadva 119ms 7332 KiB
12 Elfogadva 149ms 12792 KiB
13 Elfogadva 101ms 7208 KiB
14 Elfogadva 108ms 8024 KiB
15 Elfogadva 250ms 37512 KiB
16 Elfogadva 305ms 48804 KiB
17 Elfogadva 268ms 42692 KiB
subtask4 65/65
18 Elfogadva 356ms 15460 KiB
19 Elfogadva 351ms 10064 KiB
20 Elfogadva 695ms 59984 KiB
21 Elfogadva 732ms 53968 KiB
22 Elfogadva 479ms 31748 KiB
23 Elfogadva 365ms 10680 KiB
24 Elfogadva 633ms 47204 KiB
25 Elfogadva 523ms 25800 KiB
26 Elfogadva 216ms 5464 KiB
27 Elfogadva 527ms 32404 KiB
28 Elfogadva 890ms 98624 KiB
29 Elfogadva 168ms 11276 KiB
30 Elfogadva 523ms 47596 KiB