제출 #541278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541278		Deepesson	Cubeword (CEOI19_cubeword)	C++17	0 / 100	1200 ms	100128 KiB

cubeword

#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";
}

컴파일 시 표준 에러 (stderr) 메시지

cubeword.cpp: In function 'matriz mul(matriz, matriz)':
cubeword.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | }
      | ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 29
• Subtask 3: 0 / 34
• Subtask 4: 0 / 16