Submission #948070

#	Time	Username	Problem	Language	Result	Execution time	Memory
948070		Vladth11	Cubeword (CEOI19_cubeword)	C++14	100 / 100	365 ms	20508 KiB

cubeword

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 200002;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;

vector <pii> lung[11];

const int VMAX = 63;

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

int c[VMAX][VMAX];
int dp[VMAX][VMAX][VMAX];

void add(int &x, int val){
    x += val;
    if(x >= MOD)
        x -= MOD;
    if(x < 0)
        x += MOD;
}

map <string, int> mp;

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        string s;
        cin >> s;
        mp[s]++;
        if(mp[s] == 1)
            lung[s.size()].push_back({cod(s[0]), cod(s.back())});
        string a= s;
        reverse(a.begin(), a.end());
        mp[a]++;
        if(mp[a] == 1)
            lung[s.size()].push_back({cod(s.back()), cod(s[0])});
    }
    int sol = 0;
    for(int i = 1; i <= 10; i++){
        if(!lung[i].size()) continue;
        for(int j = 0; j < VMAX; j++) for(int t = 0; t < VMAX; t++) c[j][t] = 0;
        for(auto x : lung[i]){
            c[x.first][x.second]++;
        }
        for(int j = 0; j < VMAX; j++){
            for(int t = j; t < VMAX; t++){
                for(int k = t; k < VMAX; k++){
                    dp[j][t][k] = 0;
                    for(int aici = 0; aici < VMAX; aici++){
                        add(dp[j][t][k], (1LL * c[aici][j] * c[aici][t]) % MOD * c[aici][k] % MOD);
                    }
                    /// aici se pune
                    dp[j][k][t] = dp[t][j][k] = dp[t][k][j] = dp[k][j][t] = dp[k][t][j] = dp[j][t][k];
                }
            }
        }
        for(int a = 0; a < VMAX; a++){
            for(int b = a; b < VMAX; b++){
                for(int c = b; c < VMAX; c++){
                    for(int d = c; d < VMAX; d++){
                        int perm = 24;
                        if(a == b)
                            perm /= 2;
                        if(a == c)
                            perm /= 3;
                        if(a == d)
                            perm /= 4;
                        if(a != b && b == c){
                            perm /= 2;
                        }
                        if(a != b && b == d){
                            perm /= 3;
                        }
                        if(b != c && c == d){
                            perm /= 2;
                        }
                        add(sol, (1LL * dp[a][b][c] * dp[a][b][d]) % MOD * dp[b][c][d] % MOD * dp[a][c][d] % MOD * perm % MOD);
                    }
                }
            }
        }
    }
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int cod(char)':
cubeword.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

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