oj.uz

Submission #845549

# Submission time Handle Problem Language Result Execution time Memory
845549 2023-09-06T14:05:40 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 121 ms 16904 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int int64_t
#define ordered_set                              \
    tree<int, null_type, less<int>, rb_tree_tag, \
         tree_order_statistics_node_update>
#define F first
#define S second
#define I insert
#define PB push_back
#define POB pop_back
#define sqr(a) ((a) * (a))
#define P pop
#define max3(a, b, c) (max(a, max(b, c)))
#define max4(a, b, c, d) (max(max(a, b), max(c, d)))
#define min3(a, b, c) (min(a, min(b, c)))
#define min4(a, b, c, d) (min(min(a, b), min(c, d)))
#define MOD 1000000007
#define mod 998244353
int binpow(int a, int p, int m = MOD) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ((ans % m) * (a % m)) % m;
        a = sqr(a) % m;
        p >>= 1;
    }
    return ans;
}
const int base = 31;
const int base2 = 29;
int inversebase, inversebase2;
vector<int> p(100, 1), p2(100, 1);
vector<map<pair<int, int>, int>> a, b;
vector<map<pair<int, int>, string>> rh;
pair<int, int> hs(string s) {
    int h = 0;
    int h2 = 0;
    for (int i = 0; i < s.size(); i++) {
        h = (h + ((s[i] - 'a' + 1) * p[i]) % mod) % mod;
    }
    for (int i = 0; i < s.size(); i++) {
        h2 = (h2 + ((s[i] - 'a' + 1) * p2[i]) % MOD) % MOD;
    }
    return {h, h2};
}
pair<pair<int, int>, pair<int, int>> substr(pair<int, int> s, int n) {
    pair<pair<int, int>, pair<int, int>> ans;
    ans.F.F =
        ((s.F - (p[n] * (rh[n][s][n] - 'a' + 1)) % mod) % mod + mod) % mod;
    ans.S.F =
        (((s.F - (p[0] * (rh[n][s][0] - 'a' + 1) % mod) % mod) * inversebase) %
             mod +
         mod) %
        mod;
    ans.F.S =
        ((s.S - (p2[n] * (rh[n][s][n] - 'a' + 1)) % MOD) % MOD + MOD) % MOD;
    ans.S.S = (((s.S - (p2[0] * (rh[n][s][0] - 'a' + 1) % MOD) % MOD) *
                inversebase2) %
                   MOD +
               MOD) %
              MOD;
    return ans;
}
void solve() {
    int n, k;
    cin >> n >> k;
    a.assign(n, map<pair<int, int>, int>());
    b.assign(n, map<pair<int, int>, int>());
    rh.assign(n, map<pair<int, int>, string>());
    inversebase = binpow(base, mod - 2, mod);
    inversebase2 = binpow(base2, MOD - 2, MOD);
    for (int i = 1; i < 100; i++) p[i] = (p[i - 1] * base) % mod;
    for (int i = 1; i < 100; i++) p2[i] = (p2[i - 1] * base2) % MOD;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            string s;
            cin >> s;
            pair<int, int> h = hs(s);
            b[i][h]++;
            if (i == n - 1) a[i][h] = b[i][h];
            rh[i][h] = s;
        }
    }
    int ansi = 0;
    for (int i = n - 1; i > 0; i--) {
        for (auto x : a[i]) {
            pair<pair<int, int>, pair<int, int>> cursub = substr(x.F, i);
            a[i - 1][cursub.F] += b[i - 1][cursub.F] * x.S;
            a[i - 1][cursub.F] %= MOD;
            if (a[i - 1][cursub.F] == 0) a[i - 1].erase(cursub.F);
            if (cursub.F != cursub.S)
                a[i - 1][cursub.S] += b[i - 1][cursub.S] * x.S;
            a[i - 1][cursub.S] %= MOD;
            if (a[i - 1][cursub.S] == 0) a[i - 1].erase(cursub.S);
        }
    }
    for (auto x : a[0]) {
        ansi += x.S;
        ansi %= MOD;
    }
    cout << ansi << endl;
}
int32_t main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message

trener.cpp: In function 'std::pair<long int, long int> hs(std::string)':
trener.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
trener.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 6 ms 1368 KB Output is correct
3 Correct 8 ms 1372 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 5 ms 1076 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 4 ms 348 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 6 ms 1368 KB Output is correct
7 Correct 8 ms 1372 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 5 ms 1076 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 104 ms 15584 KB Output is correct
13 Correct 98 ms 16904 KB Output is correct
14 Correct 100 ms 16836 KB Output is correct
15 Correct 119 ms 16724 KB Output is correct
16 Correct 69 ms 1620 KB Output is correct
17 Correct 94 ms 12880 KB Output is correct
18 Correct 86 ms 13336 KB Output is correct
19 Correct 91 ms 12948 KB Output is correct
20 Correct 91 ms 12976 KB Output is correct
21 Correct 121 ms 13052 KB Output is correct
22 Correct 63 ms 1724 KB Output is correct