Submission #845168

#	Time	Username	Problem	Language	Result	Execution time	Memory
845168		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	62 ms	5720 KiB

trener

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

constexpr int md = int(1e9) + 7;
int add(int x, int y) {
  if ((x += y) >= md) {
    x -= md;
  }
  return x;
}
int mul(int x, int y) {
  return 1LL * x * y % md;
}
constexpr int base = 31;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  array<int, 26> hv{};
  iota(hv.begin(), hv.end(), 0);
  random_shuffle(hv.begin(), hv.end());
  int N, K;
  cin >> N >> K;
  vector<vector<string>> S(N, vector<string>(K));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
      cin >> S[i][j];
    }
  }
  map<int, int> ans;
  for (int i = 0; i < N; ++i) {
    map<int, int> next_ans;
    for (int j = 0; j < K; ++j) {
      int h = 0, L = -1;
      for (int k = 0; k <= i; ++k) {
        h = mul(h, base);
        h = add(h, hv[S[i][j][k] - 'a']);  
        if (k == i - 1) {
          L = h;
        }
      }
      int R = 0;
      for (int k = 1; k <= i; ++k) {
        R = mul(R, base);
        R = add(R, hv[S[i][j][k] - 'a']);
      }
      int res = (i == 0);
      res = add(res, ans[L]);
      if (R != L) {
        res = add(res, ans[R]);
      }
      next_ans[h] = add(next_ans[h], res);
    } 
    swap(ans, next_ans);
  } 
  int p = 0;
  for (auto[foo, x] : ans) {
    p = add(p, x);
  }
  cout << p << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55