Submission #742516

#	Time	Username	Problem	Language	Result	Execution time	Memory
742516		Stickfish	Cubeword (CEOI19_cubeword)	C++17	0 / 100	172 ms	7252 KiB

cubeword

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

const int MAXV = 33;
const ll MOD = 998244353;
int f[MAXV][MAXV];
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());
    for (size_t i = 0; i < v.size(); ++i) {
        if (i && v[i - 1] == v[i])
            continue;
        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 < MAXV; ++b) for (int c = 0; c < MAXV; ++c) {
        dp[a][b][c] = 0;
        for (int x = 0; x < MAXV; ++x) {
            dp[a][b][c] += 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 < MAXV; ++b) for (int c = 0; c < MAXV; ++c) for (int d = 0; d < MAXV; ++d) {
        ans += dp[a][b][c] * dp[a][b][d] % MOD * dp[a][c][d] % MOD * dp[b][c][d] % MOD;
        ans %= MOD;
    }
    return ans;
}

signed main() {
    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();
    }
    cout << ans << '\n';
}

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