Submission #1255899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255899		Faggi	Cubeword (CEOI19_cubeword)	C++20	84 / 100	1044 ms	22244 KiB

cubeword

#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MOD = 998244353;
const int ma = 58;
ll dis[8][ma][ma]; // tam, in, fin
ll memo[8][ma][ma][ma];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, i, tam, j, k, l, cant, act = 0, ant, tot = 0, u, an, bn, cn, dn;
    cin >> n;
    string s, a;
    map<string, bool> m;
    vector<ll> pos(max('z', max('Z','9')) + 1, 0);
    for (i = 'a'; i <= 'z'; i++)
        pos[i] = act++;
    for (i = 'A'; i <= 'Z'; i++)
        pos[i] = act++;
    for(i='0'; i<='9'; i++)
        pos[i]=act++;
    for (i = 0; i < n; i++)
    {
        cin >> s;
        tam = sz(s);
        a = s;
        reverse(all(a));
        if (m[s] == 0)
        {
            dis[tam-3][pos[s[0]]][pos[s.back()]]++;
            m[s] = 1;
        }
        if (a != s && m[a] == 0)
        {
            dis[tam-3][pos[a[0]]][pos[a.back()]]++;
            m[a] = 1;
        }
    }

    for (tam = 3; tam <= 10; tam++)
    {
        for (i = 0; i < ma; i++)
        {
            for (j = 0; j < ma; j++)
            {
                for (k = 0; k < ma; k++)
                {
                    for (u = 0; u < ma; u++)
                    {
                        act = 1;
                        act = (1ll*act * dis[tam-3][i][u]) % MOD;
                        act = (1ll*act * dis[tam-3][j][u]) % MOD;
                        act = (1ll*act * dis[tam-3][k][u]) % MOD;
                        memo[tam-3][i][j][k] = (act + memo[tam-3][i][j][k]) % MOD;
                    }
                }
            }
        }
    }

    for (tam = 3; tam <= 10; tam++)
    {
        for (i = 0; i < ma; i++) // 1
        {
            for (j = 0; j < ma; j++) // 2
            {
                for (k = 0; k < ma; k++) // 3
                {
                    for (l = 0; l < ma; l++) // 4
                    {
                        if (i == 5 && i == j && i == l && i == k)
                        {
                            cant = 1;
                        }
                        // 5
                        cant = 1;
                        an = memo[tam-3][i][l][k];
                        // 6
                        bn = memo[tam-3][i][j][k];
                        // 7
                        cn = memo[tam-3][j][l][k];
                        // 8
                        dn = memo[tam-3][i][j][l];
                        cant = (1ll*cant * an) % MOD;
                        cant = (1ll*cant * bn) % MOD;
                        cant = (1ll*cant * cn) % MOD;
                        cant = (1ll*cant * dn) % MOD;
                        tot = (tot + cant) % MOD;
                    }
                }
            }
        }
    }

    cout << tot;
    return 0;
}

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