Submission #533210

#	Time	Username	Problem	Language	Result	Execution time	Memory
533210		wenqi	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1188 ms	23228 KiB

cubeword

// trans rights

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

using ll = long long;

#define MOD 998244353
#define H 62

int N;
unordered_set<string> problems[11][H];
int pre[11][H][H];
int cnt[11][H][H][H];
int mapping[256];

bool is_palindrome(const string& word)
{
    return equal(word.begin(), word.end(), word.rbegin());
}

ll mul(ll x, ll y)
{
    return (x * y) % MOD;
}

template <typename ...Args>
ll mul(ll x, ll y, Args&&... args)
{
    return mul(mul(x, y), forward<Args>(args)...);
}

int main(int argc, const char *argv[])
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int x = 'a'; x <= 'z'; x++)
    {
        mapping[x] = x - 'a';
    }
    for (int x = 'A'; x <= 'Z'; x++)
    {
        mapping[x] = x - 'A' + 26;
    }
    for (int x = '0'; x <= '9'; x++)
    {
        mapping[x] = x - '0' + 52;
    }
    cin >> N;
    for (int k = 0; k < N; k++)
    {
        string word;
        cin >> word;
        problems[word.size()][mapping[word[0]]].insert(word);

        reverse(word.begin(), word.end());
        problems[word.size()][mapping[word[0]]].insert(word);
    }
    int ans = 0;

    for (int sz = 1; sz <= 10; sz++)
    {
        for (int start = 0; start < H; start++)
        {
            for (auto &word : problems[sz][start])
            {
                pre[sz][start][mapping[word.back()]]++;
            }
        }
    }

    for (int sz = 1; sz <= 10; sz++)
    {
        for (int start = 0; start < H; start++)
        {
            auto &A = pre[sz][start];
            for (int x = 0; x < H; x++)
            {
                if (A[x] == 0)
                    continue;

                for (int y = 0; y < H; y++)
                {
                    if (A[y] == 0)
                        continue;

                    for (int z = 0; z < H; z++)
                    {
                        cnt[sz][x][y][z] += mul(A[x], A[y], A[z]);
                        if (cnt[sz][x][y][z] >= MOD) cnt[sz][x][y][z] -= MOD;
                    }
                }
            }
        }
    }

    for (int sz = 1; sz <= 10; sz++)
    {
        for (int x = 0; x < H; x++)
        {
            for (int y = 0; y < H; y++)
            {
                for (int z = 0; z < H; z++)
                {
                    if (cnt[sz][x][y][z] == 0)
                        continue;

                    for (int w = 0; w < H; w++)
                    {
                        ans += mul(cnt[sz][x][y][z], cnt[sz][x][y][w], cnt[sz][x][z][w], cnt[sz][y][z][w]);
                        if (ans >= MOD) ans -= MOD;
                    }
                }
            }
        }
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int main(int, const char**)':
cubeword.cpp:54:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |         problems[word.size()][mapping[word[0]]].insert(word);
      |                                              ^
cubeword.cpp:57:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   57 |         problems[word.size()][mapping[word[0]]].insert(word);
      |                                              ^
cubeword.cpp:67:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |                 pre[sz][start][mapping[word.back()]]++;
      |                                        ~~~~~~~~~^~

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