Submission #787901

#	Time	Username	Problem	Language	Result	Execution time	Memory
787901		tvladm2009	Cubeword (CEOI19_cubeword)	C++17	100 / 100	264 ms	19676 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
const int SIGMA = 62;
const int LEN = 11;
const int M = 998244353;
int cnt[SIGMA][SIGMA];
int dp[SIGMA][SIGMA][SIGMA];
vector<pair<int, int>> info[LEN];
int n, l;

int add(int a, int b) {
  a += b;
  if (a >= M) {
    return a - M;
  }
  if (a < 0) {
    return a + M;
  }
  return a;
}

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

int mul(int a, int b) {
  return (ll) a * b % M;
}

int mul(int a, int b, int c) {
  return mul(a, mul(b, c));
}

int mul(int a, int b, int c, int d) {
  return mul(a, mul(b, c, d));
}

int decode(char ch) {
  if ('a' <= ch && ch <= 'z') {
    return ch - 'a';
  } else if ('A' <= ch && ch <= 'Z') {
    return 26 + ch - 'A';
  } else if ('0' <= ch && ch <= '9') {
    return 26 + 26 + ch - '0';
  }
  assert(0);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  /// freopen("input", "r", stdin);

  cin >> n;
  set<string> words;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    string revs = s;
    reverse(revs.begin(), revs.end());
    words.insert(s);
    words.insert(revs);
  }
  for (auto &it : words) {
    info[(int) it.size()].push_back({decode(it[0]), decode(it.back())});
  }

  int sol = 0;
  for (int len = 3; len <= 10; len++) {
    for (int i = 0; i < SIGMA; i++) {
      for (int j = 0; j < SIGMA; j++) {
        cnt[i][j] = 0;
      }
    }
    for (auto &it : info[len]) {
      cnt[it.first][it.second]++;
    }

    for (int a = 0; a < SIGMA; a++) {
      for (int b = 0; b < SIGMA; b++) {
        for (int c = 0; c < SIGMA; c++) {
          dp[a][b][c] = 0;
        }
      }
    }
    for (int a = 0; a < SIGMA; a++) {
      for (int b = a; b < SIGMA; b++) {
        for (int c = b; c < SIGMA; c++) {
          for (int d = 0; d < SIGMA; d++) {
            addup(dp[a][b][c], mul(cnt[d][a], cnt[d][b], cnt[d][c]));
          }
        }
      }
    }

    { /// 1 unique value
      for (int a = 0; a < SIGMA; a++) {
        addup(sol, mul(dp[a][a][a], dp[a][a][a], dp[a][a][a], dp[a][a][a]));
      }
    }

    { /// 2 unique values
      int aux = 0;
      for (int a = 0; a < SIGMA; a++) {
        for (int b = a + 1; b < SIGMA; b++) {
          addup(aux, mul(dp[a][a][b], dp[a][a][b], dp[a][b][b], dp[a][b][b]));
        }
      }
      addup(sol, mul(aux, 6));
      aux = 0;
      for (int a = 0; a < SIGMA; a++) {
        for (int b = a + 1; b < SIGMA; b++) {
          addup(aux, mul(dp[a][a][a], dp[a][a][b], dp[a][a][b], dp[a][a][b]));
          addup(aux, mul(dp[b][b][b], dp[a][b][b], dp[a][b][b], dp[a][b][b]));
        }
      }
      addup(sol, mul(aux, 4));
    }

    { /// 3 unique values
      int aux = 0;
      for (int a = 0; a < SIGMA; a++) {
        for (int b = a + 1; b < SIGMA; b++) {
          for (int c = b + 1; c < SIGMA; c++) {
            addup(aux, mul(dp[a][b][c], dp[a][b][c], dp[a][c][c], dp[b][c][c]));
            addup(aux, mul(dp[a][b][c], dp[a][b][c], dp[a][a][c], dp[a][a][b]));
            addup(aux, mul(dp[a][b][c], dp[a][b][c], dp[a][b][b], dp[b][b][c]));
          }
        }
      }
      addup(sol, mul(aux, 12));
    }

    { /// 4 unique values
      int aux = 0;
      for (int a = 0; a < SIGMA; a++) {
        for (int b = a + 1; b < SIGMA; b++) {
          for (int c = b + 1; c < SIGMA; c++) {
            for (int d = c + 1; d < SIGMA; d++) {
              addup(aux, mul(dp[a][b][c], dp[a][b][d], dp[a][c][d], dp[b][c][d]));
            }
          }
        }
      }
      addup(sol, mul(aux, 24));
    }
  }
  cout << sol << "\n";
  return 0;
}

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