#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 998244353;
bool isPalindrome(string &str)
{
for (ll i = 0; i < str.size() / 2; i++) if (str[i] != str[str.size() - i - 1]) return false;
return true;
}
ll combinations(ll a, ll b, ll c, ll d)
{
if (a == d) return 1;
if (a == c || b == d) return 4;
if (a == b && c == d) return 6;
if (a == b || c == d) return 12;
return 24;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n;
cin >> n;
vector<string> words(n);
for (ll i = 0; i < n; i++) cin >> words[i];
vector<char> characters;
for (ll i= 'a'; i <= 'z'; i++) characters.pb(i);
for (ll i = 'A'; i <= 'Z'; i++) characters.pb(i);
for (ll i = '0'; i <= '9'; i++) characters.pb(i);
map<char, char> charShrink;
for (ll i = 0; i < characters.size(); i++) charShrink[characters[i]] = i;
for (ll i = 0; i < n; i++) for (ll j = 0; j < words[i].size(); j++) words[i][j] = charShrink[words[i][j]];
vector<vector<string>> byLength(11);
set<string> exists;
for (ll i = 0; i < n; i++)
{
reverse(all(words[i]));
if (exists.count(words[i]) > 0) continue;
reverse(all(words[i]));
byLength[words[i].size()].pb(words[i]);
exists.insert(words[i]);
}
ll c = characters.size();
ll res = 0;
for (ll i = 3; i <= 10; i++)
{
vv amt(c, v(c, 0));
for (ll j = 0; j < byLength[i].size(); j++)
{
amt[byLength[i][j][0]][byLength[i][j].back()]++;
if (!isPalindrome(byLength[i][j])) amt[byLength[i][j].back()][byLength[i][j][0]]++;
}
vvv possibilities(c, vv(c, v(c)));
for (ll i = 0; i < c; i++)
{
for (ll j = i; j < c; j++)
{
for (ll k = j; k < c; k++)
{
for (ll l = 0; l < c; l++)
{
possibilities[i][j][k] += ((amt[i][l] * amt[j][l]) % mod) * amt[k][l];
possibilities[i][j][k] %= mod;
}
}
}
}
for (ll corner1 = 0; corner1 < c; corner1++)
{
for (ll corner2 = corner1; corner2 < c; corner2++)
{
for (ll corner3 = corner2; corner3 < c; corner3++)
{
for (ll corner4 = corner3; corner4 < c; corner4++)
{
ll cur = possibilities[corner1][corner2][corner3];
cur = (cur * possibilities[corner1][corner2][corner4]) % mod;
cur = (cur * possibilities[corner1][corner3][corner4]) % mod;
cur = (cur * possibilities[corner2][corner3][corner4]) % mod;
res = (res + cur * combinations(corner1,corner2,corner3,corner4)) % mod;
}
}
}
}
}
cout << res << "\n";
return 0;
}
Compilation message
cubeword.cpp: In function 'bool isPalindrome(std::string&)':
cubeword.cpp:32:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (ll i = 0; i < str.size() / 2; i++) if (str[i] != str[str.size() - i - 1]) return false;
| ~~^~~~~~~~~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:57:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (ll i = 0; i < characters.size(); i++) charShrink[characters[i]] = i;
| ~~^~~~~~~~~~~~~~~~~~~
cubeword.cpp:58:49: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (ll i = 0; i < n; i++) for (ll j = 0; j < words[i].size(); j++) words[i][j] = charShrink[words[i][j]];
| ~~^~~~~~~~~~~~~~~~~
cubeword.cpp:74:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (ll j = 0; j < byLength[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
15848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
15848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
15848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
15848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
