제출 #579200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579200		talant117408	Cubeword (CEOI19_cubeword)	C++17	100 / 100	561 ms	29360 KiB

cubeword

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int mod = 998244353;

ll add(ll a, ll b) {
    return ((a + b) % mod + mod) % mod;
}

ll mult(ll a, ll b) {
    return ((a * b) % mod + mod) % mod;
}

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

const int CH = 62;
ll ways[11][CH][CH], side[11][CH][CH][CH];

void solve() {
    int n;
    cin >> n;
    vector <string> v;
    set <string> st;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        auto s2 = s;
        reverse(all(s2));
        int last = sz(st);
        st.insert(s2);
        if (last != sz(st)) {
            st.insert(s);
            v.pb(s);
        }
    }
    vector <int> used(11);
    for (auto to : v) {
        if (to[0] == to.back()) {
            auto to2 = to;
            reverse(all(to2));
            ways[sz(to)][index(to.back())][index(to.back())] += 1 + (to != to2);
        }
        else {
            ways[sz(to)][index(to[0])][index(to.back())]++;
            ways[sz(to)][index(to.back())][index(to[0])]++;
        }
        used[sz(to)] = 1;
    }
    for (int j = 3; j <= 10; j++) {
        if (used[j] == 0) continue;
        for (int j2 = 0; j2 < CH; j2++)
        for (int j3 = j2; j3 < CH; j3++)
        for (int j4 = j3; j4 < CH; j4++) {
            for (int j1 = 0; j1 < CH; j1++) 
            side[j][j2][j3][j4] = add(side[j][j2][j3][j4], mult(mult(ways[j][j1][j2], ways[j][j1][j3]), ways[j][j1][j4]));
        }
    }
    
    ll ans = 0;
    
    for (int j = 3; j <= 10; j++) {
        if (used[j] == 0) continue;
        for (int _1 = 0; _1 < CH; _1++)
        for (int _4 = _1; _4 < CH; _4++)
        for (int _6 = _4; _6 < CH; _6++)
        for (int _7 = _6; _7 < CH; _7++) {
            auto res = mult(mult(side[j][_1][_4][_6], side[j][_1][_4][_7]), mult(side[j][_1][_6][_7], side[j][_4][_6][_7]));
            if (_1 == _4 && _4 == _6 && _6 == _7) {
                ans = add(ans, res);
            }
            else if ((_1 == _4 && _4 == _6) || (_4 == _6 && _6 == _7)) {
                ans = add(ans, mult(res, 4));
            }
            else if (_1 == _4 && _6 == _7) {
                ans = add(ans, mult(res, 6));
            }
            else if (_1 == _4 || _1 == _6 || _1 == _7 || _4 == _6 || _4 == _7 || _6 == _7) {
                ans = add(ans, mult(res, 12));
            }
            else {
                ans = add(ans, mult(res, 24));
            }
        }
    }
        
    cout << ans << endl;
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

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