Submission #1093738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093738		gyg	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1077 ms	19008 KiB

cubeword

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vct vector
#define str string
#define hset unordered_set
const int MX_N = 1e5 + 5, MD = 998244353;

int n;
arr<arr<arr<int, 67>, 67>, 13> cnt;

int md(int x) { return (x + MD) % MD; }

arr<arr<arr<int, 67>, 67>, 67> dp;
int cmp(int sz) {
    dp = {0};
    for (int i = 1; i <= 62; i++) 
        for (int j = 1; j <= 62; j++)
            for (int k = 1; k <= 62; k++)
                for (int l = 1; l <= 62; l++)
                    dp[i][j][k] = md(dp[i][j][k] + md(cnt[sz][i][l] * cnt[sz][j][l] * cnt[sz][k][l]));
     

    int ans = 0;
    for (int i = 1; i <= 62; i++) 
        for (int j = 1; j <= 62; j++)
            for (int k = 1; k <= 62; k++)
                for (int l = 1; l <= 62; l++)
                    ans = md(ans + md(dp[i][j][k] * dp[i][j][l]) * md(dp[i][k][l] * dp[j][k][l]));
    return ans;
}

signed main() {
    // freopen("cb.in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> n;
    hset<str> strs;
    for (int i = 1; i <= n; i++) {
        str x; cin >> x;
        strs.insert(x);
        reverse(x.begin(), x.end());
        strs.insert(x);
    }
    for (str x : strs) {
        auto indx = [](char x)->int {
            if ('a' <= x && x <= 'z') return x - 'a' + 1;
            if ('A' <= x && x <= 'Z') return 26 + x - 'A' + 1;
            return 52 + x - '0' + 1; 
        };
        cnt[x.size()][indx(x[0])][indx(x.back())]++;
    }
    
    int ans = 0;
    for (int i = 3; i <= 10; i++) {
        int nw_ans = cmp(i);
        ans = md(ans + nw_ans);
        // cout << i << ": " << nw_ans << endl;
    }   
    cout << ans << '\n';
}

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