Submission #1261780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261780		vtnoo	Cubeword (CEOI19_cubeword)	C++20	84 / 100	206 ms	16252 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int mod=998244353, N=32;
int cnt[11][54][54];
long long dp[N][N][N];
set<string> sc;

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(sc.count(s))continue;
        string s_r=s;
        reverse(s_r.begin(), s_r.end());
        sc.insert(s);
        int a=s.front()-(isupper(s.front())?'A':'a'), b=s.back()-(isupper(s.back())?'A':'a');
        int ad_a=(isupper(s.front())?16:0), ad_b=(isupper(s.back())?16:0);
        cnt[(int)s.size()][a+ad_a][b+ad_b]++;
        if(s!=s_r){
            cnt[(int)s.size()][b+ad_b][a+ad_a]++;
            sc.insert(s_r);
        }
    }
    long long ans=0;
    for(int len=3;len<=10;len++){
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<N;k++){
                    for(int l=0;l<N;l++){
                        dp[i][j][k]+=(((cnt[len][i][l]*cnt[len][j][l])%mod)*cnt[len][k][l])%mod;
                        dp[i][j][k]%=mod;
                    }   
                }
            }
        }  
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<N;k++){
                    for(int l=0;l<N;l++){
                        long long cur=dp[i][j][k];
                        cur%=mod;
                        cur*=dp[j][k][l];
                        cur%=mod;
                        cur*=dp[i][k][l];
                        cur%=mod;
                        cur*=dp[i][j][l];
                        cur%=mod;
                        ans+=cur;
                        ans%=mod;
                    }   
                }
            }
        }    
    }
    cout<<ans%mod<<endl;
}   

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