Submission #904807

#	Time	Username	Problem	Language	Result	Execution time	Memory
904807		andrei_iorgulescu	Cubeword (CEOI19_cubeword)	C++14	0 / 100	291 ms	19048 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int S = 62;
const int modulo = 998244353;
vector<string>cuv[15];
int cst[S][S];
int cost[S][S][S];

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

bool palint(string s)
{
    for (int i = 1; i < s.size() - 1; i++)
        if (s[i] != s[s.size() - 1 - i])
            return false;
    return true;
}

string inv(string s)
{
    reverse(s.begin(),s.end());
    return s;
}

map<string,bool>mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        cuv[s.size()].push_back(s);
    }
    long long ans = 0;
    for (int l = 3; l <= 10; l++)
    {
        for (int i = 0; i < S; i++)
            for (int j = 0; j < S; j++)
                cst[i][j] = 0;
        for (int i = 0; i < S; i++)
            for (int j = 0; j < S; j++)
                for (int k = 0; k < S; k++)
                    cost[i][j][k] = 0;
        for (auto it : cuv[l])
        {
            if (mp[inv(it)] == true)
                continue;
            mp[it] = true;
            cst[toint(it[0])][toint(it[l - 1])]++;
            if (it[0] != it[l - 1])
                cst[toint(it[l - 1])][toint(it[0])]++;
            else if (palint(it) == false)
                cst[toint(it[0])][toint(it[l - 1])]++;
        }
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                for (int k = 0; k < S; k++)
                {
                    for (int q = 0; q < S; q++)
                    {
                        if (1ll * cst[i][q] * cst[j][q] * cst[k][q] != 0)
                            cost[i][j][k] = (0ll + cost[i][j][k] + 1ll * cst[i][q] * cst[j][q] * cst[k][q]) % modulo;
                    }
                }
            }
        }
        for (int A = 0; A < S; A++)
        {
            for (int B = A; B < S; B++)
            {
                for (int C = B; C < S; C++)
                {
                    for (int D = C; D < S; D++)
                    {
                        if (cost[A][B][C] != 0 and cost[A][B][D] != 0 and cost[A][C][D] != 0 and cost[B][C][D] != 0)
                        {
                            int cate;
                            if (A == B and B == C and C == D)
                                cate = 1;
                            else if (A == B and B == C)
                                cate = 4;
                            else if (B == C and C == D)
                                cate = 4;
                            else if (A == B and C == D)
                                cate = 6;
                            else if (A == B or C == D)
                                cate = 12;
                            else
                                cate = 24;
                            int adg = (__int128)1 * cost[A][B][C] * cost[A][B][D] * cost[A][C][D] * cost[B][C][D] % modulo;
                            adg = 1ll * adg * cate % modulo;
                            ans += adg;
                        }
                    }
                }
            }
        }
    }
    cout << ans % modulo;
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'bool palint(std::string)':
cubeword.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 1; i < s.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~

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