#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 = 16;
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];
bool curr[MXV+1];
int getChar(char a) {
//cout << a << " " << (a >= 'a' ? (a-'a') : (16+a-'A')) << endl;
int v = a >= 'a' ? (a-'a') : (16+a-'A');
assert(v <= MXV);
return v;
}
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)); memset(curr, false, sizeof(curr));
vi used;
ll v;
for (auto i: words[l]) {
trans[i[0]][i[1]] += 1;
if (!curr[i[0]]) used.push_back(i[0]);
if (!curr[i[1]]) used.push_back(i[1]);
curr[i[0]] = curr[i[1]] = true;
if (!i[2]) trans[i[1]][i[0]] += 1;
}
for (int a: used) for (int b: used) for (int c: used) for (int d: used) {
cts[a][b][c][d] = mul({trans[a][b], trans[b][c], trans[c][d], trans[d][a]});
v = cts[a][b][c][d];
for (int cc: used) for (int dd: used) {
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 (int a: used) for (int b: used) for (int c: used) for (int d: used) {
for (int aa: used) for (int bb: used) 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 |
Incorrect |
290 ms |
20868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
20868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
20868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
20868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
