Submission #1088821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088821		juicy	Cubeword (CEOI19_cubeword)	C++17	100 / 100	236 ms	19796 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int M = 998244353, C = 62;

int cnt[C][C], f[C][C][C];

int conv(char c) {
  if ('a' <= c && c <= 'z') {
    return c - 'a';
  }
  if ('A' <= c && c <= 'Z') {
    return c - 'A' + 26;
  }
  return c - '0' + 52;
}

void add(int &x, int y) {
  if ((x += y) >= M) {
    x -= M;
  }
}

int solve(set<string> cnd) {
  memset(cnt, 0, sizeof(cnt));
  memset(f, 0, sizeof(f));
  for (auto s : cnd) {
    ++cnt[conv(s[0])][conv(s.back())];
  }
  for (int i = 0; i < C; ++i) {
    for (int j = i; j < C; ++j) {
      for (int k = j; k < C; ++k) {
        for (int l = 0; l < C; ++l) {
          add(f[i][j][k], (long long) cnt[i][l] * cnt[j][l] % M * cnt[k][l] % M);
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i < C; ++i) {
    for (int j = i; j < C; ++j) {
      for (int k = j; k < C; ++k) {
        for (int l = k; l < C; ++l) {
          int ways = (long long) f[i][j][k] * f[i][j][l] % M * f[i][k][l] % M * f[j][k][l] % M;
          if (i == l) {
            add(res, ways);
          } else if (i == k || j == l) {
            add(res, (long long) ways * 4 % M);
          } else if (i == j && l == k) {
            add(res, (long long) ways * 6 % M);
          } else if (i == j || j == k || k == l) {
            add(res, (long long) ways * 12 % M);
          } else {
            add(res, (long long) ways * 24 % M);
          }
        }
      }
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n; cin >> n;
  array<set<string>, 10> buc;
  while (n--) {
    string s; cin >> s;
    int l = s.size() - 1;
    buc[l].insert(s);
    reverse(s.begin(), s.end());
    buc[l].insert(s);
  }
  int res = 0;
  for (int i = 2; i < 10; ++i) {
    add(res, solve(buc[i]));
  }
  cout << res;
  return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 16 / 16