Submission #845286

#	Time	Username	Problem	Language	Result	Execution time	Memory
845286		vjudge1	Trener (COCI20_trener)	C++17	0 / 110	13 ms	1884 KiB

trener

#include <bits/stdc++.h>
using namespace std;
// bismillah
int main() {
  int N, K;
  cin >> N >> K;
  vector<map<string, int>> cnt(N);
  for (int i = 0;i < N; ++i) {
    for (int j = 0;j < K; ++j) {
      string s;
      cin >> s;
      cnt[i][s] += 1;
    }
  }
  int64_t mod = 1e9+7;
  map<string, int64_t> dp;
  for (int i = N-1;i >= 0; --i) {
    for (auto [s, c] : cnt[i]) {
      if (i == N-1) {
        dp[s] = c;
      }
      string a = s;
      string b = s;
      reverse(b.begin(), b.end());
      a.pop_back();
      b.pop_back();
      reverse(b.begin(), b.end());
      dp[a] += c * dp[s];
      if (a != b) dp[b] += c * dp[s];
      dp[a] %= mod;
      dp[b] %= mod;
    }
  }
  int64_t ans = 0;
  for (auto [s, c] : cnt[0]) {
    ans += dp[s] * c;
    ans %= mod;
  }
  cout << ans << '\n';
}

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