제출 #788621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788621		WLZ	Cubeword (CEOI19_cubeword)	C++17	100 / 100	348 ms	8252 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353ll;
const int MX = 62;
const vector<long long> fact = {1, 1, 2, 6, 24};

int to_int(char c) {
  if (c <= '9') {
    return c - '0';
  }
  if (c <= 'Z') {
    return c - 'A' + 10;
  }
  return c - 'a' + 36;
}

void add(long long& a, long long b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}

long long mul(long long a, long long b) {
  return (a * b) % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector< vector<string> > in(11);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    in[(int) s.length()].push_back(s);
  }
  long long ans = 0;
  for (int len = 3; len <= 10; len++) {
    if (in[len].empty()) {
      continue;
    }
    vector< vector<long long> > v(MX, vector<long long>(MX));
    vector<int> ch;
    set<string> st;
    for (auto& s : in[len]) {
      string t = s;
      reverse(t.begin(), t.end());
      if (st.count(t)) {
        continue;
      }
      int a = to_int(s[0]);
      ch.push_back(a);
      int b = to_int(s.back());
      ch.push_back(b);
      if (a == b) {
        if (s == t) {
          add(v[a][a], 1);
        } else {
          add(v[a][a], 2);
        }
      } else {
        add(v[a][b], 1);
        add(v[b][a], 1);
      }
      st.insert(s);
    }
    sort(ch.begin(), ch.end());
    ch.erase(unique(ch.begin(), ch.end()), ch.end());
    int m = (int) ch.size();
    vector< vector< vector<long long> > > d(MX, vector< vector<long long> >(MX, vector<long long>(MX, 0)));
    for (int i1 = 0; i1 < m; i1++) {
      int a = ch[i1];
      for (int i2 = i1; i2 < m; i2++) {
        int b = ch[i2];
        for (int i3 = i2; i3 < m; i3++) {
          int c = ch[i3];
          for (int j = 0; j < m; j++) {
            int k = ch[j];
            add(d[a][b][c], mul(v[a][k], mul(v[b][k], v[c][k])));
          }
          d[a][c][b] = d[b][a][c] = d[b][c][a] = d[c][a][b] = d[c][b][a] = d[a][b][c];
        }
      }
    }
    for (int i1 = 0; i1 < m; i1++) {
      int a = ch[i1];
      for (int i2 = i1; i2 < m; i2++) {
        int b = ch[i2];
        for (int i3 = i2; i3 < m; i3++) {
          int c = ch[i3];
          for (int i4 = i3; i4 < m; i4++) {
            int k = ch[i4];
            vector<int> tmp(4);
            tmp[0] = a; tmp[1] = b; tmp[2] = c; tmp[3] = k;
            sort(tmp.begin(), tmp.end());
            long long div = 24ll;
            int cur = 1;
            for (int i = 1; i < 4; i++) {
              if (tmp[i] == tmp[i - 1]) {
                cur++;
              } else {
                div /= fact[cur];
                cur = 1;
              }
            }
            div /= fact[cur];
            add(ans, mul(div, mul(d[a][b][c], mul(d[a][b][k], mul(d[a][c][k], d[b][c][k])))));
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

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