Submission #1232776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232776		Tenis0206	Cubeword (CEOI19_cubeword)	C++20	84 / 100	1196 ms	104388 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int Mod = 998244353;

int n;
int nr;

int cnt[15][155][155];
int tri[155][155][155];
int sqr[75][75][75][75];

vector<int> lst;

int get_val(int val)
{
    int st = 1;
    int dr = lst.size();
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) >> 1;
        if(lst[mij - 1] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n;
    set<string> l;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        l.insert(s);
        reverse(s.begin(), s.end());
        l.insert(s);
        lst.push_back(s.front());
        lst.push_back(s.back());
    }
    sort(lst.begin(), lst.end());
    vector<int> aux;
    for(auto it : lst)
    {
        if(aux.empty() || it != aux.back())
        {
            aux.push_back(it);
        }
    }
    lst = aux;
    nr = lst.size();
    aux.clear();
    for(auto it=l.begin();it!=l.end();it++)
    {
        string s = *it;
        ++cnt[s.size()][get_val(s.front())][get_val(s.back())];
    }
    long long rez = 0;
    for(int len=3;len<=10;len++)
    {
        for(int a=1;a<=nr;a++)
        {
            for(int h=1;h<=nr;h++)
            {
                for(int f=1;f<=nr;f++)
                {
                    tri[a][h][f] = 0;
                }
            }
        }
        for(int e=1;e<=nr;e++)
        {
            for(int a=1;a<=nr;a++)
            {
                if(!cnt[len][a][e])
                {
                    continue;
                }
                for(int h=1;h<=nr;h++)
                {
                    if(!cnt[len][h][e])
                    {
                        continue;
                    }
                    for(int f=1;f<=nr;f++)
                    {
                        tri[a][h][f] += 1LL * cnt[len][a][e] * cnt[len][h][e] % Mod * cnt[len][f][e] % Mod;
                        tri[a][h][f] %= Mod;
                    }
                }
            }
        }
        for(int a=1;a<=nr;a++)
        {
            for(int h=1;h<=nr;h++)
            {
                for(int f=1;f<=nr;f++)
                {
                    if(tri[a][h][f] == 0)
                    {
                        continue;
                    }
                    for(int c=1;c<=nr;c++)
                    {
                        sqr[a][f][h][c] = 1LL * tri[a][h][f] * tri[a][h][c] % Mod;
                    }
                }
            }
        }
        for(int a=1;a<=nr;a++)
        {
            for(int h=1;h<=nr;h++)
            {
                for(int f=1;f<=nr;f++)
                {
                    if(tri[a][h][f] == 0)
                    {
                        continue;
                    }
                    for(int c=1;c<=nr;c++)
                    {
                        rez += 1LL * sqr[a][f][h][c] * sqr[c][h][f][a] % Mod;
                        rez %= Mod;
                    }
                }
            }
        }
    }
    cout<<rez<<'\n';
    return 0;
}

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