Submission #1184110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184110		Unforgettablepl	Cubeword (CEOI19_cubeword)	C++20	84 / 100	479 ms	9148 KiB

cubeword

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

#define int long long

const int MAX_N = 52;
const int modulo = 998244353;
int DP[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++){
                    DP[a][b][c]=0;
                    for(int d=0;d<MAX_N;d++){
                        DP[a][b][c]+=(cnt[len][a][d]*cnt[len][b][d]*cnt[len][c][d])%modulo;
                        DP[a][b][c]%=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++){
                        int curr=(DP[a][b][c]*DP[a][b][d])%modulo;
                        curr*=(DP[a][c][d]*DP[b][c][d])%modulo;
                        curr%=modulo;
                        ans=(ans+curr)%modulo;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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