Submission #604783

#	Time	Username	Problem	Language	Result	Execution time	Memory
604783		1bin	Cubeword (CEOI19_cubeword)	C++14	100 / 100	428 ms	50568 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
const ll mod = 998244353;
ll n, ans, t[11][64][64], cnt[64][64][64], a, b, m[64][64][64][64];
string s;
set<string> st;

int chg(char c){
    if(c >= '0' && c <= '9') return c - '0';
    else if(c >= 'a' && c <= 'z') return c - 'a' + 10;
    else return c - 'A' + 36;
}

void solve(int l){
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < 64; i++)
        for(int j = i; j < 64; j++)
            for(int k = j; k < 64; k++)
                for(int x = 0; x < 64; x++)
                    cnt[i][j][k] += t[l][i][x] * t[l][j][x] * t[l][k][x], cnt[i][j][k] %= mod;
    
    for(int i = 0; i < 64; i++)
        for(int j = i; j < 64; j++)
            for(int k = j; k < 64; k++)
                for(int l = k; l < 64; l++)
                    ans += 24 / m[i][j][k][l] * cnt[i][j][k] % mod * cnt[i][j][l] % mod * cnt[i][k][l] % mod * cnt[j][k][l] % mod, ans %= mod;
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    for(int i = 0; i < 64; i++)
        for(int j = i; j < 64; j++)
            for(int k = j; k < 64; k++)
                for(int l = k; l < 64; l++){
                    if(i == l) m[i][j][k][l] = 24;
                    else if(i == k || j == l) m[i][j][k][l] = 6;
                    else if(i == j && k == l) m[i][j][k][l] = 4;
                    else if(i == j || j == k || k == l) m[i][j][k][l] = 2;
                    else m[i][j][k][l] = 1;
                }
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s; st.emplace(s);
        reverse(all(s)); st.emplace(s);
    }
    for(auto & s : st){
        a = chg(s[0]); b = chg(s[s.size() - 1]);
        t[s.size()][a][b]++;
    }
    
    for(int i = 3; i <= 10; i++) solve(i);
    cout << ans;
    return 0;
}

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