Submission #546567

#	Time	Username	Problem	Language	Result	Execution time	Memory
546567		LucaDantas	Cubeword (CEOI19_cubeword)	C++17	21 / 100	199 ms	16220 KiB

cubeword

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

constexpr int maxn = 6, mod = 998244353; // subtasks 1-2

int ans;

int edge[11][maxn][maxn];

int value_triad[11][maxn][maxn][maxn];

int id(char c) { return c-'a'; } // subtaks 1-2

set<string> mark;

void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }

int main() {
    int n; cin >> n;
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int rep = 0; rep < 2; rep++, reverse(s.begin(), s.end())) if(!mark.count(s)) {
            edge[s.size()][id(s[0])][id(s.back())]++;
            mark.insert(s);
        }
    }

    vector<array<int,3>> triad;
    for(int a = 0; a < maxn; a++)
        for(int b = 0; b < maxn; b++)
            for(int c = 0; c < maxn; c++)
                triad.push_back({a, b, c});


    for(int sz = 3; sz <= 10; sz++) {
        for(auto [a, b, c] : triad)
            for(int x = 0; x < maxn; x++)
                add(value_triad[sz][a][b][c], 1ll * edge[sz][x][a] * edge[sz][x][b] * edge[sz][x][c] % mod);

        for(auto [a1, b1, c1] : triad) for(auto [a2, b2, c2] : triad) {
            long long aq = 1ll * value_triad[sz][a1][b1][c1] * value_triad[sz][a2][b2][c2] % mod;
            aq *= 1ll * edge[sz][a1][b2] * edge[sz][a1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][b1][a2] * edge[sz][b1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][c1][a2] * edge[sz][c1][b2] % mod; aq %= mod;
            
            add(ans, aq);
        }
    }

    printf("%d\n", ans);
}

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