Submission #1004650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004650		vjudge1	Cubeword (CEOI19_cubeword)	C++17	84 / 100	361 ms	12704 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int MK = 32;
using vi = vector<int>;
using ll = long long;

int id2(char c) {
    if(c >= 'a' && c <= 'z') return c - 'a';
    if(c >= 'A' && c <= 'Z') return c - 'A' + 26; 
    return c - '0' + 52;
}
int id(char c) {
    if(c >= 'a' && c <= 'p') return c - 'a';
    if(c >= 'A' && c <= 'P') return c - 'A' + 16; 
}

int solve(vector<string> V) {
    if(V.empty()) return 0;
    set<string> S;
    for (auto it : V) {
        S.insert(it);
        string s2 = it;
        reverse(s2.begin(), s2.end());
        S.insert(s2);
    }
    array<array<int, MK>, MK> Fr;
    for (int i = 0; i < MK; ++i)
        for (int j = 0; j < MK; ++j)
            Fr[i][j] = 0;
    for (auto it : S) {
        int a = id(it[0]), b= id(it.back());
        ++Fr[a][b];
    }

    array<array<array<int, MK>, MK>, MK> u, v;
    for(int i = 0; i < MK; ++i)
        for(int j = 0; j < MK; ++j)
            for(int k = 0; k < MK; ++k)
                u[i][j][k] = v[i][j][k] = 0;
    for(int i = 0; i < MK; ++i)
        for(int j = 0; j < MK; ++j)
            for(int k = 0; k < MK; ++k) {
                for(int w = 0; w < MK; ++w) {
                    v[i][j][k] = (v[i][j][k] 
                    + 1ll * Fr[i][w] * Fr[j][w] % MOD * Fr[k][w] % MOD) % MOD;
                }
            }
    for(int i = 0; i < MK; ++i)
        for(int j = 0; j < MK; ++j)
            for(int k = 0; k < MK; ++k)
                u[i][j][k] = 1ll * Fr[i][k] * Fr[j][k] % MOD;
    ll re = 0;
    for(int i = 0; i < MK; ++i)
        for(int j = 0; j < MK; ++j)
            for(int k = 0; k < MK; ++k)
                for(int w = 0; w < MK; ++w) {
                    /// (v[i,j] \cdot u[k, w]) * (v[k, w] \cdot u[i, j])
                    ll v1 = 0, v2 = 0;
                    for(int a = 0; a < MK; ++a)
                        v1 = (v1 + 1ll * v[i][j][a] * u[k][w][a]);
                    v1 %= MOD;
                    ll cre = v1 * v1 % MOD * Fr[i][k] % MOD * Fr[j][w] % MOD;
                    re = (re + cre) % MOD;
                }
    return (int)re;
}

int main() {
    const int MLEN = 10;
    vector<vector<string> > V(MLEN + 1);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        V[s.size()].push_back(s);
    }
    int re = 0;
    for (int i = 0; i <= MLEN; ++i) {
        re = (re + solve(V[i])) % MOD;
    }
    cout << re << "\n";
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int solve(std::vector<std::__cxx11::basic_string<char> >)':
cubeword.cpp:61:32: warning: unused variable 'v2' [-Wunused-variable]
   61 |                     ll v1 = 0, v2 = 0;
      |                                ^~
cubeword.cpp: In function 'int id(char)':
cubeword.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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