Submission #448654

#	Time	Username	Problem	Language	Result	Execution time	Memory
448654		marcipan5000	Cubeword (CEOI19_cubeword)	C++14	84 / 100	272 ms	5376 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const long long int mo=998244353;
int n;
ll t[50][50][50];
ll g[50][50];

int turn(char x) {
    if (('a'<=x)&&('p'>=x)) {
        return(x-'a');
    }
    return(x-'A'+16);

}

void eval(string z) {
    if (z[0]!=z[z.size()-1]) {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+1)%mo;
        g[turn(z[z.size()-1])][turn(z[0])]=(g[turn(z[z.size()-1])][turn(z[0])]+1)%mo;
        return;
    }
    bool isPal=1;
    for (int i=0;i<z.size();i++) {
        if (z[i]!=z[z.size()-1-i]) {
            isPal=0;
            break;
        }
    }
    if (isPal==0) {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+2)%mo;
    } else {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+1)%mo;
    }
    return;
}

vector<string> f;

bool kis(string a,string b) {
    return((a.size()<b.size())||((a.size()==b.size())&&(a<b)));
}

ll solve(int u,int v) {
    for (int i=0;i<32;i++) {
        for (int j=0;j<32;j++) {
            g[i][j]=0;
            for (int k=0;k<32;k++) {
                t[i][j][k]=0;
            }
        }
    }
    for (int i=u;i<v;i++) {
        if ((i==u)||(f[i]!=f[i-1])) {
            eval(f[i]);
        }
    }
    for (int i=0;i<32;i++) {
        for (int j=0;j<32;j++) {
            for (int k=0;k<32;k++) {
                for (int mid=0;mid<32;mid++) {
                    t[i][j][k]=(t[i][j][k]+(((g[i][mid]*g[j][mid])%mo)*g[k][mid])%mo)%mo;
                }
            }
        }
    }
    ll ans=0;
    for (int i=0;i<32;i++) {
        for (int j=0;j<32;j++) {
            for (int k=0;k<32;k++) {
                for (int l=0;l<32;l++) {
                    ans=(ans+(((((t[i][j][k]*t[i][j][l])%mo)*t[i][k][l])%mo)*t[j][k][l])%mo)%mo;
                }
            }
        }
    }
    return(ans);
}

string flip(string a) {
    string b=a;
    for (int i=0;i<a.size();i++) {
        b[a.size()-i-1]=a[i];
    }
    if (a<b) {
        return(a);
    } else {
        return(b);
    }
}

int main()
{
    cin >> n;
    string a;
    for (int i=0;i<n;i++) {
        cin >> a;
        f.push_back(flip(a));
    }
    sort(f.begin(),f.end(),kis);
    int l=0,r=0;
    ll finAns=0;
    while (r<n) {
        while ((r<n)&&(f[l].size()==f[r].size())) {
            r++;
        }
        finAns=(finAns+solve(l,r))%mo;
        l=r;
    }
    cout << finAns << endl;
    return 0;
}

/*
for (int i=0;i<62;i++) {
    for (int j=0;j<62;j++) {
        if (g[i][j]!=0) {
            cout << i << " " << j << " " << g[i][j] << endl;
        }
    }
}
*/

Compilation message (stderr)

cubeword.cpp: In function 'void eval(std::string)':
cubeword.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<z.size();i++) {
      |                  ~^~~~~~~~~
cubeword.cpp: In function 'std::string flip(std::string)':
cubeword.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0;i<a.size();i++) {
      |                  ~^~~~~~~~~

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