oj.uz

Submission #1025493

# Submission time Handle Problem Language Result Execution time Memory
1025493 2024-07-17T05:27:03 Z 우민규(#10941) Cubeword (CEOI19_cubeword) C++17
0 / 100
 95 ms 8532 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// 1
const int SIGMA = 26;
const int MOD = 998244353;

int mul(int a, int b) { return (int64_t)a * (int64_t)b % MOD; }
int mul(int a, int b, int c) { return mul(mul(a, b), c); }
int mul(int a, int b, int c, int d) { return mul(mul(a, b), mul(c, d)); }
void add(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
int id(char c) {
  if ('a' <= c && c <= 'z') return c - 'a';
  if ('A' <= c && c <= 'Z') return c - 'A' + 26;
  return c - '0' + 52;
  //   return 0;
}

int y[SIGMA][SIGMA][SIGMA];
int ways[8][SIGMA][SIGMA];

void solve() {
  int n;
  cin >> n;
  set<string> saw;
  for (int i = 0; i < n; ++i) {
    string cur;
    cin >> cur;

    string cur_rev = cur;
    reverse(cur_rev.begin(), cur_rev.end());

    if (saw.count(cur_rev) || saw.count(cur)) continue;
    saw.insert(cur);

    int cf = id(cur.front()), cb = id(cur.back());
    if (cur == cur_rev) {
      ways[cur.size() - 3][cf][cb] += 1;
    } else {
      ways[cur.size() - 3][cf][cb] += 1;
      ways[cur.size() - 3][cb][cf] += 1;
    }
  }
  int tot_way = 0;
  for (auto& way : ways) {
    // do threes
    fill(&y[0][0][0], &y[0][0][0] + SIGMA * SIGMA * SIGMA, 0);
    for (int c1 = 0; c1 < SIGMA; ++c1)
      for (int c2 = 0; c2 < SIGMA; ++c2)
        for (int c3 = 0; c3 < SIGMA; ++c3)
          for (int c4 = 0; c4 < SIGMA; ++c4)
            y[c1][c2][c3] += mul(way[c4][c1], way[c4][c2], way[c4][c3]);

    for (int c1 = 0; c1 < SIGMA; ++c1)
      for (int c2 = 0; c2 < SIGMA; ++c2)
        for (int c3 = 0; c3 < SIGMA; ++c3)
          for (int c4 = 0; c4 < SIGMA; ++c4)
            add(tot_way, mul(y[c1][c2][c3], y[c1][c2][c4], y[c1][c3][c4],
                             y[c2][c3][c4]));
  }
  cout << tot_way << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;

  while (t--) {
    solve();
  }
  return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -