62252023-11-08 11:55:30Error42Forgó rulettkerékcpp17Wrong answer 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted3ms2020 KiB
subtask20/20
3Wrong answer3ms2240 KiB
4Wrong answer3ms2624 KiB
5Wrong answer3ms3188 KiB
6Wrong answer6ms4116 KiB
7Wrong answer6ms4336 KiB
8Wrong answer6ms4524 KiB
9Wrong answer6ms4828 KiB
subtask30/15
10Wrong answer268ms46552 KiB
11Wrong answer226ms39452 KiB
12Wrong answer280ms48644 KiB
13Wrong answer224ms44708 KiB
14Wrong answer179ms33664 KiB
15Wrong answer244ms48780 KiB
16Accepted244ms48888 KiB
17Wrong answer246ms48856 KiB
subtask40/65
18Time limit exceeded1.577s115896 KiB
19Time limit exceeded1.575s94592 KiB
20Wrong answer14ms5364 KiB
21Wrong answer910ms129300 KiB
22Time limit exceeded1.567s108568 KiB
23Wrong answer52ms15404 KiB
24Time limit exceeded1.575s112904 KiB
25Wrong answer12ms4784 KiB
26Runtime error3ms4840 KiB
27Time limit exceeded1.57s113404 KiB
28Wrong answer12ms5860 KiB
29Runtime error4ms5580 KiB
30Runtime error4ms5540 KiB