62262023-11-08 11:56:02Error42Forgó rulettkerékcpp17Wrong answer 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2012 KiB
2Accepted3ms2036 KiB
subtask20/20
3Wrong answer3ms2176 KiB
4Wrong answer3ms2548 KiB
5Wrong answer3ms2540 KiB
6Accepted4ms2620 KiB
7Accepted6ms3828 KiB
8Accepted4ms3020 KiB
9Accepted4ms3212 KiB
subtask30/15
10Wrong answer94ms12316 KiB
11Wrong answer68ms7068 KiB
12Wrong answer116ms15100 KiB
13Wrong answer92ms12252 KiB
14Wrong answer64ms8596 KiB
15Accepted216ms37548 KiB
16Accepted275ms48816 KiB
17Accepted214ms42704 KiB
subtask40/65
18Time limit exceeded1.58s98488 KiB
19Time limit exceeded1.572s93692 KiB
20Wrong answer14ms5440 KiB
21Wrong answer648ms54468 KiB
22Time limit exceeded1.569s92688 KiB
23Wrong answer34ms8400 KiB
24Time limit exceeded1.578s112628 KiB
25Wrong answer13ms5216 KiB
26Runtime error4ms5516 KiB
27Time limit exceeded1.559s112708 KiB
28Wrong answer13ms5996 KiB
29Runtime error4ms5472 KiB
30Runtime error4ms5196 KiB