Submission #779516

#	Time	Username	Problem	Language	Result	Execution time	Memory
779516		Hacv16	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1024 ms	17484 KiB

cubeword

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

#define int long long int
const int ALP = 62;
const int MOD = 998244353;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

unordered_set<string> s[15];

int32_t main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;

    for(int i = 1; i <= n; i++){
        string cur; cin >> cur;

        s[cur.size()].emplace(cur);
        reverse(cur.begin(), cur.end());
        s[cur.size()].emplace(cur);
    }

    auto getId = [&](char c)
	{
        if(c <= '9') return c - '0';
        if(c <= 'Z') return ('9' - '0' + 1) + c - 'A';
		return ('9' - '0' + 1) + ('Z' - 'A') + 1 + c - 'a';
	};

    auto solve = [&](int tam)
    {
        int dp[ALP][ALP][ALP] = { 0 };
        int freq[ALP][ALP] = { 0 };

        for(auto x : s[tam]){
            int i = getId(x[0]), j = getId(x.back());
            freq[i][j]++;
        }

        for(int a = 0; a < ALP; a++)
            for(int b = 0; b < ALP; b++)
                for(int c = 0; c < ALP; c++)
                    for(int i = 0; i < ALP; i++)
                        dp[a][b][c] = (dp[a][b][c] + (freq[a][i] * freq[b][i] * freq[c][i]) % MOD) % MOD;

        int ret = 0;

        for(int a = 0; a < ALP; a++){
            for(int b = 0; b < ALP; b++){
                for(int c = 0; c < ALP; c++){
                    for(int d = 0; d < ALP; d++){
                        int curAdd = 1;

                        curAdd = (curAdd * dp[a][b][c]) % MOD;
                        curAdd = (curAdd * dp[b][c][d]) % MOD;
                        curAdd = (curAdd * dp[a][b][d]) % MOD;
                        curAdd = (curAdd * dp[a][c][d]) % MOD;

                        ret += curAdd;
                    }
                }
            }
        }

        return ret;
    };

    int ans = 0;

    for(int i = 1; i <= 10; i++){
        if(s[i].empty()) continue;
        ans = (ans + solve(i)) % MOD;
    }

    cout << ans << '\n';
}

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