// File cubeword.cpp created on 06.10.2025 at 09:23:37
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
template<typename T>
T power(T a, i64 b) {
T res {1};
while (b) {
if (b & 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
constexpr int md = 998244353;
struct MInt {
int val;
MInt() : val(0) {}
template<typename T>
MInt(T x) {
if (-md <= x && x < md) {
val = x;
} else {
val = x % md;
}
}
int operator()() { return val; }
MInt& operator+= (MInt rhs) {
if ((val += rhs.val) >= md) {
val -= md;
}
return *this;
}
MInt& operator-= (MInt rhs) {
if ((val -= rhs.val) < 0) {
val += md;
}
return *this;
}
MInt& operator*= (MInt rhs) {
val = int(1LL * val * rhs.val % md);
return *this;
}
MInt inv() {
return power(*this, md - 2);
}
MInt& operator/= (MInt rhs) {
return *this *= rhs.inv();
}
};
MInt operator+ (MInt lhs, MInt rhs) {
return lhs += rhs;
}
MInt operator- (MInt lhs, MInt rhs) {
return lhs -= rhs;
}
MInt operator* (MInt lhs, MInt rhs) {
return lhs *= rhs;
}
MInt operator/ (MInt lhs, MInt rhs) {
return lhs /= rhs;
}
using Z = MInt;
int alp[256];
constexpr int SZ = 6;
constexpr int BASE = 67;
i64 hash(std::vector<int> v) {
i64 h = 0;
for (auto i : v) {
h = h * BASE + i;
}
return h;
}
Z solve(int n, std::vector<std::vector<int>>& vec) {
debug(n, vec);
if (vec.empty()) {
return 0;
}
std::set<i64> vis;
std::array<std::array<int, SZ + 1>, SZ + 1> cnt {};
for (auto s : vec) {
for (int _ = 0; _ < 2; ++_) {
i64 h = hash(s);
if (!vis.count(h)) {
cnt[s[0]][s[n - 1]] += 1;
vis.emplace(h);
}
std::reverse(s.begin(), s.end());
}
}
Z ans = 0;
for (int a = 1; a <= SZ; ++a) {
for (int b = 1; b <= SZ; ++b) {
for (int c = 1; c <= SZ; ++c) {
for (int d = 1; d <= SZ; ++d) {
for (int e = 1; e <= SZ; ++e) {
for (int f = 1; f <= SZ; ++f) {
for (int g = 1; g <= SZ; ++g) {
for (int h = 1; h <= SZ; ++h) {
ans += 1LL * cnt[a][b] * cnt[a][e] * cnt[a][c] * cnt[b][d] * cnt[b][g] * cnt[c][d] * cnt[c][f] * cnt[d][h] * cnt[e][g] * cnt[e][f] * cnt[f][h] * cnt[g][h];
}
}
}
}
}
}
}
}
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int cnt = 1;
for (char c = 'a'; c <= 'z'; ++c) {
alp[c] = cnt++;
}
for (char c = 'A'; c <= 'Z'; ++c) {
alp[c] = cnt++;
}
for (char c = '0'; c <= '9'; ++c) {
alp[c] = cnt++;
}
int N;
std::cin >> N;
std::vector<std::vector<int>> A(N);
for (int i = 0; i < N; ++i) {
std::string S;
std::cin >> S;
int n = int(S.size());
A[i].resize(n);
for (int j = 0; j < n; ++j) {
A[i][j] = alp[S[j]];
}
}
constexpr int MAX = 10;
std::vector<std::vector<std::vector<int>>> vec(MAX + 1);
for (int i = 0; i < N; ++i) {
vec[A[i].size()].emplace_back(A[i]);
}
Z ans = 0;
for (int i = 3; i <= MAX; ++i) {
Z x = solve(i, vec[i]);
ans += x;
}
std::cout << ans.val << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |