#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int mod = 998244353;
ll add(ll a, ll b) {
return ((a + b) % mod + mod) % mod;
}
ll mult(ll a, ll b) {
return ((a * b) % mod + mod) % mod;
}
int index(char ch) {
if ('a' <= ch && ch <= 'z') return int(ch-'a');
else if ('A' <= ch && ch <= 'Z') return int(ch-'A')+26;
else return int(ch-'0')+52;
}
ll ways[11][62][62], side1[11][62][62][62], side2[11][62][62][62];
void solve() {
int n;
cin >> n;
vector <string> v;
set <string> st;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
auto s2 = s;
reverse(all(s2));
int last = sz(st);
st.insert(s2);
if (last != sz(st)) {
st.insert(s);
v.pb(s);
}
}
vector <int> used(11);
for (auto to : v) {
if (to[0] == to.back()) {
auto to2 = to;
reverse(all(to2));
ways[sz(to)][index(to.back())][index(to.back())] += 1 + (to != to2);
}
else {
ways[sz(to)][index(to[0])][index(to.back())]++;
ways[sz(to)][index(to.back())][index(to[0])]++;
}
used[sz(to)] = 1;
}
for (int j = 3; j <= 10; j++) {
if (used[j] == 0) continue;
for (int _2 = 0; _2 < 16; _2++)
for (int _3 = 0; _3 < 16; _3++)
for (int _5 = 0; _5 < 16; _5++) {
auto &c = side1[j][_2][_3][_5];
for (int i = 0; i < 16; i++) {
auto res = mult(ways[j][i][_2], mult(ways[j][i][_3], ways[j][i][_5]));
c = add(c, res);
}
}
}
for (int j = 3; j <= 10; j++) {
if (used[j] == 0) continue;
for (int _4 = 0; _4 < 16; _4++)
for (int _6 = 0; _6 < 16; _6++)
for (int _7 = 0; _7 < 16; _7++) {
auto &c = side2[j][_4][_6][_7];
for (int i = 0; i < 16; i++) {
auto res = mult(ways[j][i][_4], mult(ways[j][i][_6], ways[j][i][_7]));
c = add(c, res);
}
}
}
ll ans = 0;
for (int j = 3; j <= 10; j++) {
if (used[j] == 0) continue;
for (int _2 = 0; _2 < 16; _2++)
for (int _3 = 0; _3 < 16; _3++)
for (int _5 = 0; _5 < 16; _5++)
for (int _4 = 0; _4 < 16; _4++)
for (int _6 = 0; _6 < 16; _6++)
for (int _7 = 0; _7 < 16; _7++) {
auto res = mult(side1[j][_2][_3][_5], side2[j][_4][_6][_7]);
res = mult(res, ways[j][_2][_6]);
res = mult(res, ways[j][_5][_6]);
res = mult(res, ways[j][_5][_7]);
res = mult(res, ways[j][_3][_7]);
res = mult(res, ways[j][_3][_4]);
res = mult(res, ways[j][_2][_4]);
ans = add(ans, res);
}
}
cout << ans << endl;
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
20684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
20684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
20684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
20684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
