제출 #546625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546625		LucaDantas	Cubeword (CEOI19_cubeword)	C++17	100 / 100	431 ms	39776 KiB

cubeword

#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 = 62, mod = 998244353; // subtasks 1-2

int ans;

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

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

int id(char c) { if(c >= '0' && c <= '9') return c-'0'+52; if(c >= 'a') return c-'a'; return 26+c-'A'; } // subtaks 1-2

set<string> mark;

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

int D[11][maxn][maxn][maxn], perm[maxn][maxn][maxn][maxn];

const int f[] = {1, 1, 2, 6, 24};

int choose(int a, int b) { return f[a] / (f[b]*f[a-b]); }

void pre() {
    int cnt[maxn]{};
    for(int a = 0; a < maxn; a++) for(int b = a; b < maxn; b++) for(int c = b; c < maxn; c++) for(int d = c; d < maxn; d++) {
        ++cnt[a], ++cnt[b], ++cnt[c], ++cnt[d];
        perm[a][b][c][d] = 1;
        int tot = 4;
        for(int i : {a, b, c, d}) {
            perm[a][b][c][d] *= choose(tot, cnt[i]), tot -= cnt[i];
            cnt[i] = 0;
        }
    }
}

int main() {
    pre();

    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);
        }
    }


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

    for(int sz = 3; sz <= 10; sz++) {
        for(int a = 0; a < maxn; a++) for(int b = a; b < maxn; b++) for(int c = b; c < maxn; c++) for(int d = c; d < maxn; d++) {
            add(ans, 1ll * D[sz][a][b][c] * D[sz][a][b][d] % mod * D[sz][a][c][d] % mod * D[sz][b][c][d] % mod * perm[a][b][c][d] % mod);
        }
    }

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

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