62252023-11-08 11:55:30Error42Forgó rulettkerékcpp17Hibás válasz 0/1001.577s129300 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<(ll)1e14 + 31>;

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
1Elfogadva3ms1828 KiB
2Elfogadva3ms2020 KiB
subtask20/20
3Hibás válasz3ms2240 KiB
4Hibás válasz3ms2624 KiB
5Hibás válasz3ms3188 KiB
6Hibás válasz6ms4116 KiB
7Hibás válasz6ms4336 KiB
8Hibás válasz6ms4524 KiB
9Hibás válasz6ms4828 KiB
subtask30/15
10Hibás válasz268ms46552 KiB
11Hibás válasz226ms39452 KiB
12Hibás válasz280ms48644 KiB
13Hibás válasz224ms44708 KiB
14Hibás válasz179ms33664 KiB
15Hibás válasz244ms48780 KiB
16Elfogadva244ms48888 KiB
17Hibás válasz246ms48856 KiB
subtask40/65
18Időlimit túllépés1.577s115896 KiB
19Időlimit túllépés1.575s94592 KiB
20Hibás válasz14ms5364 KiB
21Hibás válasz910ms129300 KiB
22Időlimit túllépés1.567s108568 KiB
23Hibás válasz52ms15404 KiB
24Időlimit túllépés1.575s112904 KiB
25Hibás válasz12ms4784 KiB
26Futási hiba3ms4840 KiB
27Időlimit túllépés1.57s113404 KiB
28Hibás válasz12ms5860 KiB
29Futási hiba4ms5580 KiB
30Futási hiba4ms5540 KiB