#include <bits/stdc++.h>
using i64 = long long;
constexpr int L = 8;
constexpr i64 mod = 998244353;
/*
value of C
subtask 1 : 6
subtask 2 : 16
subtask 3 : 32
subtask 4 : 62
*/
int main() {
int N;
std::cin >> N;
std::vector<std::string> words(N);
for (auto &e : words) {
std::cin >> e;
}
std::vector<std::vector<int>> W(N);
std::vector<char> chars;
for (const auto &e : words) {
for (const auto c : e) {
chars.push_back(c);
}
}
std::sort(chars.begin(), chars.end());
chars.erase(std::unique(chars.begin(), chars.end()), chars.end());
for (int i = 0; i < N; ++i) {
for (const auto e : words[i]) {
W[i].push_back((int)(std::lower_bound(chars.begin(), chars.end(), e) - chars.begin()));
}
}
const int C = chars.size();
std::array<std::vector<std::vector<i64>>, L> U;
for (auto &vec : U) {
vec.resize(C);
for (auto &vec2 : vec) {
vec2.assign(C, 0);
}
}
for (int i = 0; i < N; ++i) {
const int a = (int)W[i].size();
++U[a - 3][W[i][0]][W[i][a - 1]];
auto w2 = W[i];
std::reverse(w2.begin(), w2.end());
if (W[i] != w2) {
++U[a - 3][w2[0]][w2[a - 1]];
}
}
auto solve = [&](std::vector<std::vector<i64>> V) -> i64 {
// C^8
auto countPair = [&](int a, int b) {
if (a > b) std::swap(a, b);
return V[a][b];
};
std::map<std::array<int, 4>, i64> memo;
auto calc = [&](std::array<int, 4> cList) -> i64 {
i64 ret = 1;
for (int x = 0; x < 4; ++x) {
i64 s = 0;
for (int i = 0; i < C; ++i) {
i64 c = 1;
for (int j = 0; j < 4; ++j) {
if (x != j) c *= countPair(i, cList[j]);
}
s += c;
s %= mod;
}
ret *= s;
ret %= mod;
}
return ret;
};
i64 res = 0;
for (int a = 0; a < C; ++a) {
for (int b = 0; b < C; ++b) {
for (int c = 0; c < C; ++c) {
for (int d = 0; d < C; ++d) {
std::array<int, 4> list = {{a, b, c, d}};
std::sort(list.begin(), list.end());
if (memo.find(list) != memo.end()) {
res += memo[list];
} else {
res += calc(list);
}
res %= mod;
}
}
}
}
return res;
};
i64 answer = 0;
for (const auto &e : U) {
answer += solve(e);
answer %= mod;
}
std::cout << answer << std::endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
12352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
12352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
12352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
12352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
