Submission #572382

#	Time	Username	Problem	Language	Result	Execution time	Memory
572382		piOOE	Cubeword (CEOI19_cubeword)	C++17	84 / 100	752 ms	15312 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 8, A = 32, L = 11, mod = 998244353;
const ll infL = 3e18;

int g[N][3] = {{1, 2, 4},
               {0, 3, 5},
               {0, 3, 6},
               {1, 2, 7},
               {0, 5, 6},
               {1, 4, 7},
               {2, 4, 7},
               {3, 5, 6}};

int n;
int cnt[A][A][L], used[N], dp2[A][A][A], dp7[A][A][A], dp1[A][A][A], dp4[A][A][A];
int ans = 0, len = 0;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<string> stt;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        string ss = s;
        reverse(all(ss));
        stt.push_back(ss);
        stt.push_back(s);
    }
    sort(all(stt));
    stt.resize(unique(all(stt)) - begin(stt));
    for (string s: stt) {
        ++cnt[islower(s[0]) ? int(s[0] - 'a') : s[0] - 'A' + 16][islower(s.back()) ? int(s.back() - 'a') : s.back() -
                                                                                                           'A' + 16][sz(
                s)];
    }
    for (len = 1; len < L; ++len) {
        {
            //2
            memset(used, -1, sizeof(used));
            for (int x0 = 0; x0 < A; ++x0) {
                used[0] = x0;
                for (int x3 = 0; x3 < A; ++x3) {
                    used[3] = x3;
                    for (int x6 = 0; x6 < A; ++x6) {
                        used[6] = x6;
                        int sum = 0;
                        for (int x = 0; x < A; ++x) {
                            int now = 1;
                            for (int to: g[2]) {
                                assert(used[to] != -1);
                                now = (now * (ll) cnt[x][used[to]][len]) % mod;
                            }
                            sum = (sum + now) % mod;
                        }
                        dp2[x0][x3][x6] = sum;
                    }
                }
            }
        }
        {
            //1
            memset(used, -1, sizeof(used));
            for (int x0 = 0; x0 < A; ++x0) {
                used[0] = x0;
                for (int x3 = 0; x3 < A; ++x3) {
                    used[3] = x3;
                    for (int x5 = 0; x5 < A; ++x5) {
                        used[5] = x5;
                        int sum = 0;
                        for (int x = 0; x < A; ++x) {
                            int now = 1;
                            for (int to: g[1]) {
                                assert(used[to] != -1);
                                now = (now * (ll) cnt[x][used[to]][len]) % mod;
                            }
                            sum = (sum + now) % mod;
                        }
                        dp1[x0][x3][x5] = sum;
                    }
                }
            }
        }
        {
            //7
            memset(used, -1, sizeof(used));
            for (int x6 = 0; x6 < A; ++x6) {
                used[6] = x6;
                for (int x3 = 0; x3 < A; ++x3) {
                    used[3] = x3;
                    for (int x5 = 0; x5 < A; ++x5) {
                        used[5] = x5;
                        int sum = 0;
                        for (int x = 0; x < A; ++x) {
                            int now = 1;
                            for (int to: g[7]) {
                                assert(used[to] != -1);
                                now = (now * (ll) cnt[x][used[to]][len]) % mod;
                            }
                            sum = (sum + now) % mod;
                        }
                        dp7[x3][x5][x6] = sum;
                    }
                }
            }
        }
        {
            //4
            memset(used, -1, sizeof(used));
            for (int x0 = 0; x0 < A; ++x0) {
                used[0] = x0;
                for (int x6 = 0; x6 < A; ++x6) {
                    used[6] = x6;
                    for (int x5 = 0; x5 < A; ++x5) {
                        used[5] = x5;
                        int sum = 0;
                        for (int x = 0; x < A; ++x) {
                            int now = 1;
                            for (int to: g[4]) {
                                assert(used[to] != -1);
                                now = (now * (ll) cnt[x][used[to]][len]) % mod;
                            }
                            sum = (sum + now) % mod;
                        }
                        dp4[x0][x5][x6] = sum;
                    }
                }
            }
        }
        for (int x0 = 0; x0 < A; ++x0) {
            for (int x3 = 0; x3 < A; ++x3) {
                for (int x5 = 0; x5 < A; ++x5) {
                    for (int x6 = 0; x6 < A; ++x6) {
                        ans = (ans + dp4[x0][x5][x6] * (ll) dp7[x3][x5][x6] % mod * (ll) dp1[x0][x3][x5] % mod *
                                     (ll) dp2[x0][x3][x6]) % mod;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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