Submission #703954

#	Time	Username	Problem	Language	Result	Execution time	Memory
703954		LittleCube	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1151 ms	9832 KiB

cubeword

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

const int C = 62;
const ll mod = 998'244'353;
int N;
vector<string> v[11];
ll ans, way[C][C][C], edge[C][C];

int id(char c)
{
    if ('a' <= c && c <= 'z')
        return c - 'a';
    else if ('A' <= c && c <= 'Z')
        return c - 'A' + 26;
    else
        return c - '0' + 52;
}

signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        v[s.size()].emplace_back(s);
        reverse(s.begin(), s.end());
        v[s.size()].emplace_back(s);
    }
    for (int s = 3; s <= 10; s++)
    {
        sort(v[s].begin(), v[s].end());
        v[s].resize(unique(v[s].begin(), v[s].end()) - v[s].begin());
        for (int i = 0; i < C; i++)
            for (int j = 0; j < C; j++)
                for (int k = 0; k < C; k++)
                    way[i][j][k] = edge[i][j] = 0;
        for (auto t : v[s])
            edge[id(t.front())][id(t.back())]++;
        for (int i = 0; i < C; i++)
            for (int j = 0; j < C; j++)
                for (int k = 0; k < C; k++)
                    for (int l = 0; l < C; l++)
                        way[i][j][k] = (way[i][j][k] + edge[l][i] * edge[l][j] % mod * edge[l][k]) % mod;

        for (int i = 0; i < C; i++)
            for (int j = 0; j < C; j++)
                for (int k = 0; k < C; k++)
                    for (int l = 0; l < C; l++)
                        ans = (ans + way[i][j][k] * way[i][j][l] % mod * way[i][k][l] % mod * way[j][k][l]) % mod;
    }
    cout << ans << '\n';
}

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