62262023-11-08 11:56:02Error42Forgó rulettkerékcpp17Hibás válasz 0/1001.58s112708 KiB
#include <iostream>
#include <map>
#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<1'000'000'007>;

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

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

    mod const fp = mod(31).pow(m - 1);

    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)];

        hashes[ll(cur_hash)]++;

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

            hashes[ll(cur_hash)]++;
        }
    }

    cout << ans << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2012 KiB
2Elfogadva3ms2036 KiB
subtask20/20
3Hibás válasz3ms2176 KiB
4Hibás válasz3ms2548 KiB
5Hibás válasz3ms2540 KiB
6Elfogadva4ms2620 KiB
7Elfogadva6ms3828 KiB
8Elfogadva4ms3020 KiB
9Elfogadva4ms3212 KiB
subtask30/15
10Hibás válasz94ms12316 KiB
11Hibás válasz68ms7068 KiB
12Hibás válasz116ms15100 KiB
13Hibás válasz92ms12252 KiB
14Hibás válasz64ms8596 KiB
15Elfogadva216ms37548 KiB
16Elfogadva275ms48816 KiB
17Elfogadva214ms42704 KiB
subtask40/65
18Időlimit túllépés1.58s98488 KiB
19Időlimit túllépés1.572s93692 KiB
20Hibás válasz14ms5440 KiB
21Hibás válasz648ms54468 KiB
22Időlimit túllépés1.569s92688 KiB
23Hibás válasz34ms8400 KiB
24Időlimit túllépés1.578s112628 KiB
25Hibás válasz13ms5216 KiB
26Futási hiba4ms5516 KiB
27Időlimit túllépés1.559s112708 KiB
28Hibás válasz13ms5996 KiB
29Futási hiba4ms5472 KiB
30Futási hiba4ms5196 KiB