Submission #696109

#	Time	Username	Problem	Language	Result	Execution time	Memory
696109		sugartheanh	Cubeword (CEOI19_cubeword)	C++14	100 / 100	275 ms	22348 KiB

cubeword

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int M = 62;
constexpr int L = 8;
constexpr int MOD = 998244353;

typedef long long ll;

int Q[L][M][M];
int DP[L][M][M][M];


int id(char c) {
    if (c >= 'a' && c <= 'z') {
        return c - 'a';
    } else if (c >= 'A' && c <= 'Z') {
        return c - 'A' + 26;
    } else {
        return c - '0' + 52;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    set<string> W;
    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        W.insert(S);
        reverse(S.begin(),S.end());
        W.insert(S);
    }

    for (const string&w: W) {
        Q[w.size()-3][id(w[0])][id(w.back())]++;
    }

    for (int s = 0; s < L; s++) {
        for (int i = 0; i < M; i++) {
            for (int j = i; j < M; j++) {
                for (int k = j; k < M; k++) {
                    for (int l = 0; l < M; l++) {
                        DP[s][i][j][k] += ( (ll)Q[s][i][l] * (ll)Q[s][j][l] * (ll)Q[s][k][l] ) % MOD;
                        if (DP[s][i][j][k] >= MOD) DP[s][i][j][k] -= MOD;
                    }
                }
            }
        }
    }

    vector<int> Mul{24, 12, 12, 4, 12, 6, 4, 1};
    ll ans = 0;
    for (int s = 0; s < L; s++) {
        for (int i = 0; i < M; i++) {
            for (int j = i; j < M; j++) {
                for (int k = j; k < M; k++) {
                    for (int l = k; l < M; l++) {
                        int q = (i==j)<<2 | (j==k)<<1 | (k==l);
                        ans += ((ll)DP[s][i][j][k] * (ll)DP[s][i][j][l] % MOD) * ((ll)DP[s][i][k][l] * (ll)DP[s][j][k][l] % MOD) % MOD * Mul[q]; 
                    }
                }
            }
        }
    }
    cout << ans % MOD << '\n';
}

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