Submission #1006377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006377		MilosMilutinovic	Trener (COCI20_trener)	C++14	22 / 110	640 ms	2388 KiB

trener

#include <bits/stdc++.h>

using namespace std;

const int B1 = 77777;
const int B2 = 12345;

const int md1 = 1e9 + 7;
const int md2 = 1e9 + 9;

int add(int a, int b, int md) {
  return a + b < md ? a + b : a + b - md;
}

void ckadd(int& a, int b, int md) {
  a = add(a, b, md);
}

int mul(int a, int b, int md) {
  return a * 1LL * b % md;
}

void ckmul(int& a, int b, int md) {
  a = mul(a, b, md);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  map<pair<int, int>, int> mp;
  vector<vector<int>> dp(n + 1, vector<int>(k));
  for (int i = 1; i <= n; i++) {
    vector<string> s(k);
    for (int j = 0; j < k; j++) {
      cin >> s[j];
      if (i == 1) {
        dp[i][j] = 1;
      }
    }
    for (int j = 0; j < k; j++) {
      map<pair<int, int>, bool> was;
      for (int l = 0; l < i; l++) {
        int pw1 = 1;
        int pw2 = 1;
        int hs1 = 0;
        int hs2 = 0;
        for (int r = l; r < i; r++) {
          int v = (int) (s[j][r] - 'a' + 1);
          ckadd(hs1, mul(v, pw1, md1), md1);
          ckadd(hs2, mul(v, pw1, md1), md1);
          if (!was[{hs1, hs2}]) {
            ckadd(dp[i][j], mp[{hs1, hs2}], md1);
            was[{hs1, hs2}] = true;
          }
          ckmul(pw1, B1, md1);
          ckmul(pw2, B2, md2);
        }
      }
    }
    mp.clear();
    for (int j = 0; j < k; j++) {
      int pw1 = 1;
      int pw2 = 1;
      int hs1 = 0;
      int hs2 = 0;
      for (int p = 0; p < i; p++) {
        int v = (int) (s[j][p] - 'a' + 1);
        ckadd(hs1, mul(v, pw1, md1), md1);
        ckadd(hs2, mul(v, pw1, md1), md1);
        ckmul(pw1, B1, md1);
        ckmul(pw2, B2, md2);
      }
      ckadd(mp[{hs1, hs2}], dp[i][j], md1);
    }
  }
  int res = 0;
  for (int i = 0; i < k; i++) {
    ckadd(res, dp[n][i], md1);
  }
  cout << res << '\n';
  return 0;
}

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