제출 #1261765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261765		vtnoo	Cubeword (CEOI19_cubeword)	C++20	50 / 100	108 ms	15664 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int mod=998244353, N=16;
int cnt[11][26][26];
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()-'a', b=s.back()-'a';
        cnt[(int)s.size()][a][b]++;
        if(s!=s_r){
            cnt[(int)s.size()][b][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: 0 / 34
• Subtask 4: 0 / 16