oj.uz

답안 #546569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546569 2022-04-07T20:30:47 Z LucaDantas Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 15036 KB 
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 16, 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 a = 0; a < maxn; a++) for(int b = 0; b < maxn; b++) for(int c = 0; c < maxn; c++)
            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(int a1 = 0; a1 < maxn; a1++) for(int b1 = 0; b1 < maxn; b1++) for(int c1 = 0; c1 < maxn; c1++)
        for(int a2 = 0; a2 < maxn; a2++) for(int b2 = 0; b2 < maxn; b2++) for(int c2 = 0; c2 < maxn; c2++) {
        // 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
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1196 ms 15036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1196 ms 15036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1196 ms 15036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1196 ms 15036 KB Time limit exceeded
2 Halted 0 ms 0 KB -