제출 #445706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445706		Haruto810198	Cubeword (CEOI19_cubeword)	C++17	100 / 100	616 ms	8992 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 65;
int SZ = 64; /// Subtask 4

int n;
map<char, int> char_id;

vector<string> strings[11];

set<string> edges[MAX][MAX];

int edge_cnt[MAX][MAX];
int half_cnt[MAX][MAX][MAX];

int res;

int fac[5] = {1, 1, 2, 6, 24};

int per(vi arr){
    int cnt = 0;
    int pv = -1;
    int ret = fac[szof(arr)];
    for(int i : arr){
        if(i == pv){
            cnt++;
        }
        else{
            ret /= fac[cnt];
            cnt = 1;
        }
        pv = i;
    }
    ret /= fac[cnt];
    return ret;
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    /// a~p -> 0~15
    for(char i='a'; i<='p'; i++){
        char_id[i] = i - 'a';
    }

    /// A~P -> 16~31
    for(char i='A'; i<='P'; i++){
        char_id[i] = i - 'A' + 16;
    }

    /// q~z -> 32~41
    for(char i='q'; i<='z'; i++){
        char_id[i] = i - 'a' + 16;
    }

    /// Q~Z -> 42~51
    for(char i='Q'; i<='Z'; i++){
        char_id[i] = i - 'A' + 26;
    }

    /// 0~9 -> 52~61
    for(char i='0'; i<='9'; i++){
        char_id[i] = i - '0' + 52;
    }

    cin>>n;

    FOR(i, 1, n, 1){
        string str;
        cin>>str;
        strings[szof(str)].pb(str);
    }

    /// L = len. of strings
    FOR(L, 3, 10, 1){

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edges[i][j].clear();
            }
        }

        for(string S : strings[L]){
            int u = char_id[ S[0] ];
            int v = char_id[ S[L-1] ];
            edges[u][v].insert(S);
            reverse(S.begin(), S.end());
            edges[v][u].insert(S);
        }

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edge_cnt[i][j] = szof(edges[i][j]);
            }
        }

        /// one half

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                FOR(k, 0, SZ-1, 1){
                    half_cnt[i][j][k] = 0;
                }
            }
        }

        FOR(B, 0, SZ-1, 1){
            FOR(D, B, SZ-1, 1){
                FOR(E, D, SZ-1, 1){

                    FOR(A, 0, SZ-1, 1){
                        half_cnt[B][D][E] += edge_cnt[A][B] * edge_cnt[A][D] * edge_cnt[A][E];
                        half_cnt[B][D][E] %= mod;
                    }

                    // half_cnt[B][E][D] = half_cnt[D][B][E] = half_cnt[D][E][B] = half_cnt[E][B][D] = half_cnt[E][D][B] = half_cnt[B][D][E];

                }
            }
        }

        /// another half

        FOR(A, 0, SZ-1, 1){
            FOR(B, A, SZ-1, 1){
                FOR(D, B, SZ-1, 1){
                    FOR(E, D, SZ-1, 1){

                        int val = (((half_cnt[A][B][D] * half_cnt[A][B][E]) % mod) * ((half_cnt[A][D][E] * half_cnt[B][D][E]) % mod)) % mod;
                        res += val * per({A, B, D, E});
                        res %= mod;

                    }
                }
            }
        }

    }

    cout<<res<<'\n';

    return 0;

}

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