#include <bits/stdc++.h>
#define MAX 105000
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
std::vector<std::string> words[MAX];
int N;
const long long MOD = 998244353;
long long tabela[300][300];
typedef std::array<std::array<long long,2>,2> matriz;
matriz mul(matriz a,matriz b){
matriz c={};
for(int i=0;i!=2;++i){
for(int j=0;j!=2;++j){
for(int k=0;k!=2;++k){
c[i][j]=(c[i][j]+(a[i][j]*b[j][k]))%MOD;
}
}
}
}
matriz gera(long long delta){
matriz a={};
a[0][0]=1;
a[1][1]=1;
a[1][0]=delta;
return a;
}
int letra(char ch){
if(ch>='a'&&ch<='p'){
return ch-'a';
}else {
return (ch-'A')+('p'-'a'+1);
}
}
void iniciar(int x){
std::map<std::string,bool> mapa;
memset(&tabela[0][0],0,sizeof(tabela));
for(auto&z:words[x]){
mapa[z]=true;
std::reverse(z.begin(),z.end());
mapa[z]=true;
}
for(auto&x:mapa){
tabela[letra(x.first[0])][letra(x.first.back())]++;
}
}
#define TOT 33
long long tab[TOT][TOT][TOT][TOT][10];
matriz neutro;
long long solve(void){
///Fase 6 O(N^4)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
for(int k=0;k!=TOT;++k){
tab[0][i][j][k][6]=0;
for(int u=0;u!=TOT;++u){
tab[0][i][j][k][6]=(tab[0][i][j][k][6]+((tabela[i][u]*tabela[j][u])%MOD)*tabela[k][u])%MOD;
}
}
}
}
///Fase 5 O(N^5)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
for(int k=0;k!=TOT;++k){
for(int u=0;u!=TOT;++u){
tab[i][j][k][u][5]=0;
for(int v=0;v!=TOT;++v){
tab[i][j][k][u][5]=(
tab[i][j][k][u][5]+
((tab[0][v][k][u][6]*(
(tabela[i][v]*tabela[j][v])%MOD
))
%MOD))
%MOD;
}
}
}
}
}
///Fase 4 O(N^5)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
for(int k=0;k!=TOT;++k){
for(int u=0;u!=TOT;++u){
tab[i][j][k][u][4]=0;
for(int v=0;v!=TOT;++v){
tab[i][j][k][u][4]=(
tab[i][j][k][u][4]+
((tab[i][j][v][u][5]*(
(tabela[i][v]*tabela[k][v])%MOD
))
%MOD))
%MOD;
}
}
}
}
}
///Fase 3 O(N^4)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
for(int k=0;k!=TOT;++k){
tab[i][j][k][0][3]=0;
for(int v=0;v!=TOT;++v){
tab[i][j][k][0][3]=(
tab[i][j][k][0][3]+
((tab[i][j][k][v][4]*(
(tabela[j][v]*tabela[k][v])%MOD
))
%MOD))
%MOD;
}
}
}
}
///Fase 2 O(N^4)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
for(int k=0;k!=TOT;++k){
tab[i][j][k][0][2]=0;
for(int v=0;v!=TOT;++v){
tab[i][j][k][0][2]=(
tab[i][j][k][0][2]+
((tab[v][j][k][0][3]*(
(tabela[i][v])%MOD
))
%MOD))
%MOD;
}
}
}
}
///Fase 1 O(N^3)
for(int i=0;i!=TOT;++i){
for(int j=0;j!=TOT;++j){
tab[i][j][0][0][1]=0;
for(int v=0;v!=TOT;++v){
tab[i][j][0][0][1]=(
tab[i][j][0][0][1]+
((tab[i][j][v][0][2]*(
(tabela[i][v])%MOD
))
%MOD))
%MOD;
}
}
}
///Fase 0 O(N^2)
for(int i=0;i!=TOT;++i){
tab[i][0][0][0][0]=0;
for(int v=0;v!=TOT;++v){
tab[i][0][0][0][0]=(
tab[i][0][0][0][0]+
((tab[i][v][0][0][1]*(
(tabela[i][v])%MOD
))
%MOD))
%MOD;
}
}
long long resp=0;
for(int i=0;i!=TOT;++i)resp=(resp+tab[i][0][0][0][0])%MOD;
return resp;
}
int main()
{
neutro[0][0]=neutro[1][1]=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>N;
for(int i=0;i!=N;++i){
std::string k;
std::cin>>k;
words[k.size()].push_back(k);
}
long long tot = 0;
for(int i=3;i!=11;++i){
iniciar(i);
tot = (tot+solve())%MOD;
}
std::cout<<tot<<"\n";
}
Compilation message
cubeword.cpp: In function 'matriz mul(matriz, matriz)':
cubeword.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
19 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1200 ms |
100128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1200 ms |
100128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1200 ms |
100128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1200 ms |
100128 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
