Submission #446280

#	Time	Username	Problem	Language	Result	Execution time	Memory
446280		benedict0724	Cubeword (CEOI19_cubeword)	C++17	100 / 100	432 ms	27076 KiB

cubeword

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

ll cnt[62][62][11];
ll Pre[62][62][62][11];
ll ans = 0;
const ll mod = 998244353;
map<string, int> M;

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

int main()
{
    int n; cin >> n;
    for(int i=1;i<=n;i++)
    {
        string s; cin >> s;

        string p = s;
        reverse(p.begin(), p.end());
        if(M[p]) continue;

        M[s] = 1;
        int t = s.size();
        int a = f(s[0]);
        int b = f(s[t-1]);
        bool flag = true;
        for(int i=0;i<t;i++)
        {
            if(s[i] != s[t-i-1]) flag = false;
        }

        if(a != b) { cnt[a][b][t]++; cnt[b][a][t]++; }
        else if(flag) cnt[a][a][t]++;
        else cnt[a][a][t] += 2;
    }

    for(int t=3;t<=10;t++)
    {
        for(int i=0;i<62;i++)
        {
            for(int j=i;j<62;j++)
            {
                for(int k=j;k<62;k++)
                {
                    for(int p=0;p<62;p++)
                    {
                        ll tmp = 1;
                        tmp *= cnt[i][p][t];
                        tmp %= mod;
                        tmp *= cnt[j][p][t];
                        tmp %= mod;
                        tmp *= cnt[k][p][t];
                        tmp %= mod;
                        Pre[i][j][k][t] += tmp;
                    }
                }
            }
        }
    }

    for(int t=3;t<=10;t++)
    {
        for(int a=0;a<62;a++)
        {
            for(int b=a;b<62;b++)
            {
                for(int c=b;c<62;c++)
                {
                    for(int d=c;d<62;d++)
                    {
                        ll tmp = 1;
                        tmp *= Pre[a][b][c][t];
                        tmp %= mod;
                        tmp *= Pre[a][b][d][t];
                        tmp %= mod;
                        tmp *= Pre[a][c][d][t];
                        tmp %= mod;
                        tmp *= Pre[b][c][d][t];
                        tmp %= mod;

                        if(a == d) tmp *= 1;
                        else if(a == c || b == d) tmp *= 4;
                        else if(a == b && c == d) tmp *= 6;
                        else if(a == b || b == c || c == d) tmp *= 12;
                        else tmp *= 24;
                        ans = (ans + tmp)%mod;
                    }
                }
            }
        }
    }

    cout << ans;
}

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