Submission #742529

#	Time	Username	Problem	Language	Result	Execution time	Memory
742529		Stickfish	Cubeword (CEOI19_cubeword)	C++17	100 / 100	226 ms	10472 KiB

cubeword

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>
using namespace std;
using ll = long long;

const int MAXV = 63;
const ll MOD = 998244353;
ll f[MAXV][MAXV];
ll cnt_repeat[8];
ll dp[MAXV][MAXV][MAXV];

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

void get_edg(vector<string> v) {
    for (int p = 0; p < MAXV; ++p) {
        for (int q = 0; q < MAXV; ++q) {
            f[p][q] = 0;
        }
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (size_t i = 0; i < v.size(); ++i) {
        int p = to_int(v[i][0]);
        int q = to_int(v[i].back());
        ++f[p][q];
    }
}

void get_dp() {
    for (int a = 0; a < MAXV; ++a) for (int b = 0; b <= a; ++b) for (int c = 0; c <= b; ++c) {
        dp[a][b][c] = 0;
        for (int x = 0; x < MAXV; ++x) {
            dp[a][b][c] += 1ll * f[a][x] * f[b][x] * f[c][x];
            dp[a][b][c] %= MOD;
        }
    }
}

ll get_ans() {
    ll ans = 0;
    get_dp();
    for (int a = 0; a < MAXV; ++a) for (int b = 0; b <= a; ++b) for (int c = 0; c <= b; ++c) for (int d = 0; d <= c; ++d) {
        int rpat = int(a > b) + int(b > c) * 2 + int(c > d) * 4;
        ans += dp[a][b][c] * dp[a][b][d] % MOD * dp[a][c][d] % MOD * dp[b][c][d] % MOD * cnt_repeat[rpat];
        ans %= MOD;
    }
    return ans;
}

signed main() {
    cnt_repeat[0] = 1;
    cnt_repeat[1] = 4;
    cnt_repeat[2] = 6;
    cnt_repeat[3] = 12;
    cnt_repeat[4] = 4;
    cnt_repeat[5] = 12;
    cnt_repeat[6] = 12;
    cnt_repeat[7] = 24;
    int n;
    cin >> n;
    vector<vector<string>> vals(11);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        vals[s.size()].push_back(s);
        reverse(s.begin(), s.end());
        vals[s.size()].push_back(s);
    }
    ll ans = 0;
    for (int t = 0; t < 11; ++t) {
        if (vals[t].empty())
            continue;
        get_edg(vals[t]);
        ans += get_ans();
    }
    ans %= MOD;
    cout << ans << '\n';
}

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