#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
const int N = 1e5 + 5;
const int M = 65;
const int mod = 119 << 23 | 1;
int is[M][M], pre[M][M][M];
int bp(int a, int b){
int c=1;
while(b){
if(b&1) c = c * 1ll * a % mod;
a = a * 1ll * a % mod, b >>= 1;
} return c;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<string> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
for(auto& x : a[i]){
if('a' <= x && x <= 'z') x = x - 'a';
if('A' <= x && x <= 'Z') x = x - 'A' + 26;
if('0' <= x && x <= '9') x = x - '0' + 52;
}
string s = a[i];
reverse(s.begin(), s.end());
a[i] = min(a[i], s);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
vector<string> b;
for(int i=0;i<n;i++){
if(!i || a[i] != a[i-1]) b.push_back(a[i]);
}
swap(a, b);
sort(a.begin(), a.end(), [&](string& a, string& b){
return a.size() < b.size();
});
int l = 0, tot = 0;
for(int s=3;s<=10;s++){
memset(is, 0, sizeof is);
int k = l;
while(l < n && (int)a[l].size() == s){
string b = a[l];
reverse(b.begin(), b.end());
is[a[l][0]][a[l][s - 1]]++;
if(a[l] != b) is[a[l][s - 1]][a[l][0]]++;
l++;
}
if(l == k) continue;
memset(pre, 0, sizeof pre);
//~ for(int i=0;i<26;i++){
//~ for(int j=0;j<26;j++){
//~ cout<<is[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
for(int k=0;k<M;k++){
for(int l=0;l<M;l++){
pre[i][j][k] = (pre[i][j][k] + is[i][l] * 1ll * is[j][l] % mod * is[k][l]) % mod;
}
//~ if(pre[i][j][k]){
//~ cout<<i<<" "<<j<<" "<<k<<"\n";
//~ cout<<pre[i][j][k]<<"\n";
//~ }
}
}
}
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
for(int k=0;k<M;k++){
for(int l=0;l<M;l++){
int res = 1;
res = res * 1ll * pre[i][j][k] % mod;
res = res * 1ll * pre[i][j][l] % mod;
res = res * 1ll * pre[i][k][l] % mod;
res = res * 1ll * pre[j][k][l] % mod;
tot = (tot + res) % mod;
}
}
}
}
}
//~ cout<<tot<<"\n";
//~ tot = tot * 1ll * bp(6, mod - 2) % mod;
cout<<tot<<"\n";
}
Compilation message
cubeword.cpp: In function 'int main()':
cubeword.cpp:57:14: warning: array subscript has type 'char' [-Wchar-subscripts]
57 | is[a[l][0]][a[l][s - 1]]++;
| ^
cubeword.cpp:57:27: warning: array subscript has type 'char' [-Wchar-subscripts]
57 | is[a[l][0]][a[l][s - 1]]++;
| ^
cubeword.cpp:58:32: warning: array subscript has type 'char' [-Wchar-subscripts]
58 | if(a[l] != b) is[a[l][s - 1]][a[l][0]]++;
| ^
cubeword.cpp:58:41: warning: array subscript has type 'char' [-Wchar-subscripts]
58 | if(a[l] != b) is[a[l][s - 1]][a[l][0]]++;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
7620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
7620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
7620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
7620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
