제출 #1183894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183894		Unforgettablepl	Cubeword (CEOI19_cubeword)	C++20	0 / 100	1199 ms	107644 KiB

cubeword

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

#define int long long

const int MAX_N = 52;
const int modulo = 998244353;
int DP[2][MAX_N][MAX_N][MAX_N][MAX_N];
int cnt[11][MAX_N][MAX_N];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    unordered_set<string> taken;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        if(taken.count(s))continue;
        int len = s.size();
        int st = 0;
        if('a'<=s[0] and s[0]<='z')st=s[0]-'a';
        else if('A'<=s[0] and s[0]<='Z')st=s[0]-'A'+26;
        else st=s[0]-'0'+52;
        int ed = 0;
        if('a'<=s[len-1] and s[len-1]<='z')ed=s[len-1]-'a';
        else if('A'<=s[len-1] and s[len-1]<='Z')ed=s[len-1]-'A'+26;
        else ed=s[len-1]-'0'+52;
        string rev = s;
        reverse(rev.begin(),rev.end());
        taken.insert(rev);
        cnt[len][st][ed]++;
        if(rev!=s)cnt[len][ed][st]++;
    }
    int ans = 0;
    for(int len=3;len<=10;len++){
        
        // for(int a=0;a<MAX_N;a++){
        //     for(int b=0;b<MAX_N;b++){
        //         for(int c=0;c<MAX_N;c++){
        //             for(int d=0;d<MAX_N;d++){
        //                 for(int e=0;e<MAX_N;e++){
        //                     for(int f=0;f<MAX_N;f++){
        //                         for(int g=0;g<MAX_N;g++){
        //                             for(int h=0;h<MAX_N;h++){
        //                                 int curr = 1;
        //                                 curr=(curr*cnt[len][a][b])%modulo;
        //                                 curr=(curr*cnt[len][b][c])%modulo;
        //                                 curr=(curr*cnt[len][c][d])%modulo;
        //                                 curr=(curr*cnt[len][d][a])%modulo;
        //                                 curr=(curr*cnt[len][e][f])%modulo;
        //                                 curr=(curr*cnt[len][f][g])%modulo;
        //                                 curr=(curr*cnt[len][g][h])%modulo;
        //                                 curr=(curr*cnt[len][h][e])%modulo;
        //                                 curr=(curr*cnt[len][a][e])%modulo;
        //                                 curr=(curr*cnt[len][b][f])%modulo;
        //                                 curr=(curr*cnt[len][c][g])%modulo;
        //                                 curr=(curr*cnt[len][d][h])%modulo;
        //                                 ans=(ans+curr)%modulo;
        //                             }
        //                         }
        //                     }
        //                 }
        //             }
        //         }
        //     }
        // }
        // continue;
        for(int a=0;a<MAX_N;a++){
            for(int b=0;b<MAX_N;b++){
                for(int c=0;c<MAX_N;c++){
                    for(int d=0;d<MAX_N;d++){
                        DP[0][a][b][c][d]=(cnt[len][a][b]*cnt[len][b][c])%modulo;
                        DP[0][a][b][c][d]*=(cnt[len][c][d]*cnt[len][d][a])%modulo;
                        DP[0][a][b][c][d]%=modulo;
                    }
                }
            }
        }
        for(int a=0;a<MAX_N;a++){
            for(int b=0;b<MAX_N;b++){
                for(int c=0;c<MAX_N;c++){
                    for(int d=0;d<MAX_N;d++){
                        DP[1][a][b][c][d]=0;
                        for(int e=0;e<MAX_N;e++){
                            DP[1][a][b][c][d]+=(cnt[len][a][e]*DP[0][e][b][c][d])%modulo;
                            DP[1][a][b][c][d]%=modulo;
                        }
                    }
                }
            }
        }
        for(int a=0;a<MAX_N;a++){
            for(int b=0;b<MAX_N;b++){
                for(int c=0;c<MAX_N;c++){
                    for(int d=0;d<MAX_N;d++){
                        DP[0][a][b][c][d]=0;
                        for(int e=0;e<MAX_N;e++){
                            DP[0][a][b][c][d]+=(cnt[len][b][e]*DP[1][a][e][c][d])%modulo;
                            DP[0][a][b][c][d]%=modulo;
                        }
                        DP[0][a][b][c][d]*=cnt[len][a][b];
                        DP[0][a][b][c][d]%=modulo;
                    }
                }
            }
        }
        for(int a=0;a<MAX_N;a++){
            for(int b=0;b<MAX_N;b++){
                for(int c=0;c<MAX_N;c++){
                    for(int d=0;d<MAX_N;d++){
                        DP[1][a][b][c][d]=0;
                        for(int e=0;e<MAX_N;e++){
                            DP[1][a][b][c][d]+=(cnt[len][c][e]*DP[0][a][b][e][d])%modulo;
                            DP[1][a][b][c][d]%=modulo;
                        }
                        DP[1][a][b][c][d]*=cnt[len][b][c];
                        DP[1][a][b][c][d]%=modulo;
                    }
                }
            }
        }
        for(int a=0;a<MAX_N;a++){
            for(int b=0;b<MAX_N;b++){
                for(int c=0;c<MAX_N;c++){
                    for(int d=0;d<MAX_N;d++){
                        DP[0][a][b][c][d]=0;
                        for(int e=0;e<MAX_N;e++){
                            DP[0][a][b][c][d]+=(cnt[len][d][e]*DP[1][a][b][c][e])%modulo;
                            DP[0][a][b][c][d]%=modulo;
                        }
                        DP[0][a][b][c][d]*=(cnt[len][c][d]*cnt[len][a][d])%modulo;
                        DP[0][a][b][c][d]%=modulo;
                        ans+=DP[0][a][b][c][d];
                        ans%=modulo;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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