#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
const int MXV = 10;
const ll mod = 998244353;
ll trans[MXV+1][MXV+1], ct[MXV+1][MXV+1][MXV+1][MXV+1], cts[MXV+1][MXV+1][MXV+1][MXV+1];
int getChar(char a) {
//cout << a << " " << (a >= 'a' ? (a-'a') : (16+a-'A')) << endl;
return a >= 'a' ? (a-'a') : (16+a-'A');
}
ll mul(vector<ll> nums) {
ll ans = nums[0];
for_(i, 1, nums.size()) ans = (ans * nums[i]) % mod;
return ans;
}
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<vector<vi>> words(11);
vector<set<string>> raw(11);
for_(i, 0, n) {
string s; cin >> s;
if (raw[s.size()].count(s)) continue;
int a = getChar(s[0]), b = getChar(s.back()), c;
string temp = s;
reverse(temp.begin(), temp.end());
c = temp == s;
words[s.size()].push_back({a, b, c});
raw[s.size()].insert(s);
if (!c) raw[s.size()].insert(temp);
}
ll ans = 0;
for_(l, 3, 11) {
if (!words[l].size()) continue;
//cout << l << "-------" << endl;
memset(trans, 0, sizeof(trans)); memset(ct, 0, sizeof(ct)); memset(ct, 0, sizeof(cts));
ll v;
for (auto i: words[l]) {
trans[i[0]][i[1]] += 1;
if (!i[2]) trans[i[1]][i[0]] += 1;
}
for_(a, 0, MXV+1) for_(b, 0, MXV+1) for_(c, 0, MXV+1) for_(d, 0, MXV+1) {
cts[a][b][c][d] = mul({trans[a][b], trans[b][c], trans[c][d], trans[d][a]});
//cout << (char) ('a'+a) << " " << (char) ('a'+b) << " " << (char) ('a'+c) << " " << (char) ('a'+d) << " " << cts[a][b][c][d] << endl;
v = cts[a][b][c][d];
for_(cc, 0, MXV+1) for_(dd, 0, MXV+1) {
ct[a][b][cc][dd] += mul({v, trans[c][cc], trans[d][dd]});
if (ct[a][b][cc][dd] >= mod) ct[a][b][cc][dd] -= mod;
}
}
for_(a, 0, MXV+1) for_(b, 0, MXV+1) for_(c, 0, MXV+1) for_(d, 0, MXV+1) {
for_(aa, 0, MXV+1) for_(bb, 0, MXV+1) ans += mul({cts[a][b][c][d], ct[aa][bb][c][d], trans[a][aa], trans[b][bb]});
if (ans >= mod) ans -= mod;
}
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1188 ms |
20116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1188 ms |
20116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1188 ms |
20116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1188 ms |
20116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
