Submission #1038305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038305		vjudge1	Cubeword (CEOI19_cubeword)	C++17	100 / 100	276 ms	19140 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    
    long long int M = 998244353;
    map<char, int> m;
    for(int i=0; i<26; i++) m['a'+(char)i]=i;
    for(int i=0; i<26; i++) m['A'+(char)i]=i+26;
    for(int i=0; i<10; i++) m['0'+(char)i]=i+52;
    map<string, int> omega;
    
    long long int U[10][62][62];
    for(int k=0; k<10; k++) for(int i=0; i<62; i++) for(int j=0; j<62; j++) U[k][i][j]=0;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        string t="";
        int l=s.size()-1;
        for(int i=0; i<=l; i++){
            t.push_back(s[l-i]);
        }
        if(omega[s]==0){
            omega[s]++;
            U[l][m[s[0]]][m[s[l]]]++;
        }
        if(omega[t]==0){
            omega[t]++;
            U[l][m[t[0]]][m[t[l]]]++;
        }
    }
    long long int H[62][62][62];
    long long int ans=0;
    for(int v=2; v<10; v++){
        for(int k=0; k<62; k++) for(int i=k; i<62; i++) for(int j=i; j<62; j++) H[k][i][j]=0;
        for(int i=0; i<62; i++){
            for(int j=i; j<62; j++){
                for(int k=j; k<62; k++){
                    for(int l=0; l<62; l++){
                        H[i][j][k] = (H[i][j][k]+(((U[v][i][l]*U[v][j][l])%M)*U[v][k][l]))%M;
                    }
                }
            }
        }
        for(int i=0; i<62; i++){
            for(int j=i; j<62; j++){
                for(int k=j; k<62; k++){
                    for(int l=k; l<62; l++){
                        long long int V = (((H[i][j][k]*H[i][j][l])%M)*((H[i][k][l]*H[j][k][l])%M))%M;
                        if(i!=j){
                            V*=4;
                            if(j!=k){
                                V*=3;
                                if(k!=l) V*=2;
                            }else if(j!=l){
                                V*=3;
                            }
                        }else if(j!=k){
                            if(l!=k){
                                V*=12;
                            }else{
                                V*=6;
                            }
                        }else if(k!=l){
                            V*=4;
                        }
                        ans+=V;
                        ans%=M;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

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