#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_set>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 1e5 + 9, mod = 998244353;
int n;
int a[11][62][62][2];
bool palind(string s) {
int l(0), r(s.size() - 1);
while (l < r) {
if (s[l] != s[r]) return false;
++l, --r;
}
return true;
}
vector<int> ch;
bool flag;
int num(char c) {
if (!flag) {
if ('a' <= c && c <= 'z') return c - 'a';
if ('A' <= c && c <= 'Z') return c - 'A' + 26;
if ('0' <= c && c <= '9') return c - '0' + 52;
return -1;
}
else {
return lower_bound(all(ch), c) - ch.begin();
}
}
ll pw[N];
ll calc(int len, int i, int j) {
if (i > j) swap(i, j);
if (i != j) return a[len][i][j][0];
return a[len][i][j][1] + pw[a[len][i][j][0]];
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n;
pw[1] = 2;
for (int i = 2; i <= n; ++i) {
pw[i] = pw[i - 1] << 1;
if (pw[i] > mod) pw[i] -= mod;
}
unordered_set<string> S;
for (int ii = 0; ii < n; ++ii) {
string s; cin >> s;
if (S.count(s)) continue;
int i = num(s[0]), j = num(s.back());
if (i > j) swap(i, j);
ch.push_back(i);
ch.push_back(j);
++a[s.size()][i][j][palind(s)];
reverse(all(s));
S.insert(s);
}
sort(all(ch));
ch.resize(unique(all(ch)) - ch.begin());
flag = true;
for (int len = 3; len <= 10; ++len)
for (int i = 0; i < ch.size(); ++i)
for (int j = i; j < ch.size(); ++j) {
int i1 = ch[i], i2 = ch[j];
a[len][i][j][0] = a[len][i1][i2][0];
a[len][i][j][1] = a[len][i1][i2][1];
}
ll ans(0);
for (int len = 3; len <= 10; ++len)
for (int i1 = 0; i1 < ch.size(); ++i1)
for (int i2 = 0; i2 < ch.size(); ++i2)
for (int i3 = 0; i3 < ch.size(); ++i3)
for (int i4 = 0; i4 < ch.size(); ++i4)
for (int i5 = 0; i5 < ch.size(); ++i5)
for (int i6 = 0; i6 < ch.size(); ++i6)
for (int i7 = 0; i7 < ch.size(); ++i7)
for (int i8 = 0; i8 < ch.size(); ++i8) {
ans += calc(len, i1, i2) * calc(len, i2, i3) % mod * calc(len, i3, i4) % mod * calc(len, i4, i1) % mod
* calc(len, i1, i5) % mod * calc(len, i2, i6) % mod * calc(len, i3, i7) % mod * calc(len, i4, i8) % mod
* calc(len, i5, i6) % mod * calc(len, i6, i7) % mod * calc(len, i7, i8) % mod * calc(len, i8, i5);
ans %= mod;
}
cout << ans << '\n';
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
Compilation message
cubeword.cpp: In function 'int main()':
cubeword.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < ch.size(); ++i)
| ~~^~~~~~~~~~~
cubeword.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int j = i; j < ch.size(); ++j) {
| ~~^~~~~~~~~~~
cubeword.cpp:81:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i1 = 0; i1 < ch.size(); ++i1)
| ~~~^~~~~~~~~~~
cubeword.cpp:82:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i2 = 0; i2 < ch.size(); ++i2)
| ~~~^~~~~~~~~~~
cubeword.cpp:83:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i3 = 0; i3 < ch.size(); ++i3)
| ~~~^~~~~~~~~~~
cubeword.cpp:84:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i4 = 0; i4 < ch.size(); ++i4)
| ~~~^~~~~~~~~~~
cubeword.cpp:85:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i5 = 0; i5 < ch.size(); ++i5)
| ~~~^~~~~~~~~~~
cubeword.cpp:86:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i6 = 0; i6 < ch.size(); ++i6)
| ~~~^~~~~~~~~~~
cubeword.cpp:87:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i7 = 0; i7 < ch.size(); ++i7)
| ~~~^~~~~~~~~~~
cubeword.cpp:88:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i8 = 0; i8 < ch.size(); ++i8) {
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
9164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
9164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
9164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
596 ms |
9164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
