oj.uz

Submission #572412

# Submission time Handle Problem Language Result Execution time Memory
572412 2022-06-04T10:43:04 Z piOOE Cubeword (CEOI19_cubeword) C++17
84 / 100
 253 ms 16760 KB 
#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;


namespace Ment {
    template<typename T>
    T inverse(T a, T m) {
        T u = 0, v = 1;
        while (a != 0) {
            T t = m / a;
            m -= t * a;
            swap(a, m);
            u -= t * v;
            swap(u, v);
        }
        assert(m == 1);
        return u;
    }

    template<typename T>
    class Modular {
    public:
        using Type = typename decay<decltype(T::value)>::type;

        constexpr Modular() : value() {}

        template<typename U>
        Modular(const U &x) {
            value = normalize(x);
        }

        template<typename U>
        static Type normalize(const U &x) {
            Type v;
            if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
            else v = static_cast<Type>(x % mod());
            if (v < 0) v += mod();
            return v;
        }

        const Type &operator()() const { return value; }

        template<typename U>
        explicit operator U() const { return static_cast<U>(value); }

        constexpr static Type mod() { return T::value; }

        Modular &operator+=(const Modular &other) {
            value += other.value - mod();
            value += (value >> 31) & mod();
            return *this;
        }

        Modular &operator-=(const Modular &other) {
            value -= other.value;
            value += (value >> 31) & mod();
            return *this;
        }

        template<typename U>
        Modular &operator+=(const U &other) { return *this += Modular(other); }

        template<typename U>
        Modular &operator-=(const U &other) { return *this -= Modular(other); }

        Modular &operator++() { return *this += 1; }

        Modular &operator--() { return *this -= 1; }

        Modular operator++(int) {
            Modular result(*this);
            *this += 1;
            return result;
        }

        Modular operator--(int) {
            Modular result(*this);
            *this -= 1;
            return result;
        }

        Modular operator-() const { return Modular(-value); }

        template<typename U = T>
        typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &
        operator*=(const Modular &rhs) {
#ifdef _WIN32
            uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
            uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
            asm(
                    "divl %4; \n\t"
                    : "=a" (d), "=d" (m)
                    : "d" (xh), "a" (xl), "r" (mod())
                    );
            value = m;
#else
            value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
            return *this;
        }

        template<typename U = T>
        typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &
        operator*=(const Modular &rhs) {
            int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
            value = normalize(value * rhs.value - q * mod());
            return *this;
        }

        template<typename U = T>
        typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &
        operator*=(const Modular &rhs) {
            value = normalize(value * rhs.value);
            return *this;
        }

        Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }

        template<typename U>
        friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);

        template<typename U>
        friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);

        template<typename U>
        friend std::istream &operator>>(std::istream &stream, Modular<U> &number);

    private:
        Type value;
    };

    template<typename T>
    bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }

    template<typename T, typename U>
    bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }

    template<typename T, typename U>
    bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }

    template<typename T>
    bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }

    template<typename T, typename U>
    bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }

    template<typename T, typename U>
    bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }

    template<typename T>
    bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }

    template<typename T>
    Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T, typename U>
    Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T, typename U>
    Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }

    template<typename T>
    Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T, typename U>
    Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T, typename U>
    Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }

    template<typename T>
    Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T, typename U>
    Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T, typename U>
    Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }

    template<typename T>
    Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }

    template<typename T, typename U>
    Modular<T> power(const Modular<T> &a, const U &b) {
        assert(b >= 0);
        Modular<T> x = a, res = 1;
        U p = b;
        while (p > 0) {
            if (p & 1) res *= x;
            x *= x;
            p >>= 1;
        }
        return res;
    }

    template<typename T>
    string to_string(const Modular<T> &number) {
        return to_string(number());
    }

    template<typename T>
    std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
        return stream << number();
    }

    template<typename T>
    std::istream &operator>>(std::istream &stream, Modular<T> &number) {
        typename common_type<typename Modular<T>::Type, int64_t>::type x;
        stream >> x;
        number.value = Modular<T>::normalize(x);
        return stream;
    }

    constexpr int md = 998244353;
    using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
}
using Ment::Mint;


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 = 10;
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;
Mint cnt[L][A][A], dp2[A][A][A], dp7[A][A][A], dp1[A][A][A], dp4[A][A][A];
Mint ans = 0;
int len = 0;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    unordered_set<string> stt;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        string ss = s;
        reverse(all(ss));
        if (ss != s)
            stt.insert(ss);
        stt.insert(s);
    }
    for (string s: stt) {
        ++cnt[sz(s) - 1][get(s[0])][get(s.back())];
    }
    for (len = 0; len < L; ++len) {
        for (int x0 = 0; x0 < A; ++x0) {
            for (int x3 = 0; x3 < A; ++x3) {
                for (int x6 = 0; x6 < A; ++x6) {
                    Mint sum = 0;
                    for (int x = 0; x < A; ++x) {
                        sum += cnt[len][x][x0] * cnt[len][x][x3] * cnt[len][x][x6];
                    }
                    dp2[x0][x3][x6] = dp7[x0][x3][x6] = dp1[x0][x3][x6] = dp4[x0][x3][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] * dp7[x3][x5][x6] * dp1[x0][x3][x5] *
                                     dp2[x0][x3][x6]);
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 16060 KB Output is correct
2 Correct 174 ms 16112 KB Output is correct
3 Correct 213 ms 16088 KB Output is correct
4 Correct 164 ms 16052 KB Output is correct
5 Correct 169 ms 16060 KB Output is correct
6 Correct 166 ms 16028 KB Output is correct
7 Correct 221 ms 16092 KB Output is correct
8 Correct 174 ms 16096 KB Output is correct
9 Correct 199 ms 16060 KB Output is correct
10 Correct 189 ms 16148 KB Output is correct
11 Correct 169 ms 16056 KB Output is correct
12 Correct 182 ms 16104 KB Output is correct
13 Correct 206 ms 16060 KB Output is correct
14 Correct 182 ms 16096 KB Output is correct
15 Correct 173 ms 16116 KB Output is correct
16 Correct 192 ms 16060 KB Output is correct
17 Correct 174 ms 16052 KB Output is correct
18 Correct 169 ms 16064 KB Output is correct
19 Correct 198 ms 16036 KB Output is correct
20 Correct 179 ms 16020 KB Output is correct
21 Correct 167 ms 16064 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 16060 KB Output is correct
2 Correct 174 ms 16112 KB Output is correct
3 Correct 213 ms 16088 KB Output is correct
4 Correct 164 ms 16052 KB Output is correct
5 Correct 169 ms 16060 KB Output is correct
6 Correct 166 ms 16028 KB Output is correct
7 Correct 221 ms 16092 KB Output is correct
8 Correct 174 ms 16096 KB Output is correct
9 Correct 199 ms 16060 KB Output is correct
10 Correct 189 ms 16148 KB Output is correct
11 Correct 169 ms 16056 KB Output is correct
12 Correct 182 ms 16104 KB Output is correct
13 Correct 206 ms 16060 KB Output is correct
14 Correct 182 ms 16096 KB Output is correct
15 Correct 173 ms 16116 KB Output is correct
16 Correct 192 ms 16060 KB Output is correct
17 Correct 174 ms 16052 KB Output is correct
18 Correct 169 ms 16064 KB Output is correct
19 Correct 198 ms 16036 KB Output is correct
20 Correct 179 ms 16020 KB Output is correct
21 Correct 167 ms 16064 KB Output is correct
22 Correct 177 ms 16380 KB Output is correct
23 Correct 188 ms 16388 KB Output is correct
24 Correct 176 ms 16436 KB Output is correct
25 Correct 211 ms 16500 KB Output is correct
26 Correct 186 ms 16476 KB Output is correct
27 Correct 186 ms 16452 KB Output is correct
28 Correct 185 ms 16496 KB Output is correct
29 Correct 179 ms 16412 KB Output is correct
30 Correct 173 ms 16440 KB Output is correct
31 Correct 173 ms 16504 KB Output is correct
32 Correct 188 ms 16376 KB Output is correct
33 Correct 179 ms 16428 KB Output is correct
34 Correct 180 ms 16488 KB Output is correct
35 Correct 219 ms 16452 KB Output is correct
36 Correct 173 ms 16388 KB Output is correct
37 Correct 172 ms 16472 KB Output is correct
38 Correct 173 ms 16376 KB Output is correct
39 Correct 185 ms 16468 KB Output is correct
40 Correct 189 ms 16432 KB Output is correct
41 Correct 175 ms 16404 KB Output is correct
42 Correct 176 ms 16504 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 16060 KB Output is correct
2 Correct 174 ms 16112 KB Output is correct
3 Correct 213 ms 16088 KB Output is correct
4 Correct 164 ms 16052 KB Output is correct
5 Correct 169 ms 16060 KB Output is correct
6 Correct 166 ms 16028 KB Output is correct
7 Correct 221 ms 16092 KB Output is correct
8 Correct 174 ms 16096 KB Output is correct
9 Correct 199 ms 16060 KB Output is correct
10 Correct 189 ms 16148 KB Output is correct
11 Correct 169 ms 16056 KB Output is correct
12 Correct 182 ms 16104 KB Output is correct
13 Correct 206 ms 16060 KB Output is correct
14 Correct 182 ms 16096 KB Output is correct
15 Correct 173 ms 16116 KB Output is correct
16 Correct 192 ms 16060 KB Output is correct
17 Correct 174 ms 16052 KB Output is correct
18 Correct 169 ms 16064 KB Output is correct
19 Correct 198 ms 16036 KB Output is correct
20 Correct 179 ms 16020 KB Output is correct
21 Correct 167 ms 16064 KB Output is correct
22 Correct 177 ms 16380 KB Output is correct
23 Correct 188 ms 16388 KB Output is correct
24 Correct 176 ms 16436 KB Output is correct
25 Correct 211 ms 16500 KB Output is correct
26 Correct 186 ms 16476 KB Output is correct
27 Correct 186 ms 16452 KB Output is correct
28 Correct 185 ms 16496 KB Output is correct
29 Correct 179 ms 16412 KB Output is correct
30 Correct 173 ms 16440 KB Output is correct
31 Correct 173 ms 16504 KB Output is correct
32 Correct 188 ms 16376 KB Output is correct
33 Correct 179 ms 16428 KB Output is correct
34 Correct 180 ms 16488 KB Output is correct
35 Correct 219 ms 16452 KB Output is correct
36 Correct 173 ms 16388 KB Output is correct
37 Correct 172 ms 16472 KB Output is correct
38 Correct 173 ms 16376 KB Output is correct
39 Correct 185 ms 16468 KB Output is correct
40 Correct 189 ms 16432 KB Output is correct
41 Correct 175 ms 16404 KB Output is correct
42 Correct 176 ms 16504 KB Output is correct
43 Correct 240 ms 16552 KB Output is correct
44 Correct 216 ms 16568 KB Output is correct
45 Correct 215 ms 16608 KB Output is correct
46 Correct 231 ms 16572 KB Output is correct
47 Correct 222 ms 16628 KB Output is correct
48 Correct 219 ms 16520 KB Output is correct
49 Correct 221 ms 16584 KB Output is correct
50 Correct 241 ms 16532 KB Output is correct
51 Correct 219 ms 16544 KB Output is correct
52 Correct 208 ms 16628 KB Output is correct
53 Correct 240 ms 16616 KB Output is correct
54 Correct 212 ms 16532 KB Output is correct
55 Correct 253 ms 16532 KB Output is correct
56 Correct 221 ms 16632 KB Output is correct
57 Correct 223 ms 16504 KB Output is correct
58 Correct 222 ms 16604 KB Output is correct
59 Correct 227 ms 16596 KB Output is correct
60 Correct 220 ms 16512 KB Output is correct
61 Correct 238 ms 16520 KB Output is correct
62 Correct 225 ms 16520 KB Output is correct
63 Correct 221 ms 16628 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 16060 KB Output is correct
2 Correct 174 ms 16112 KB Output is correct
3 Correct 213 ms 16088 KB Output is correct
4 Correct 164 ms 16052 KB Output is correct
5 Correct 169 ms 16060 KB Output is correct
6 Correct 166 ms 16028 KB Output is correct
7 Correct 221 ms 16092 KB Output is correct
8 Correct 174 ms 16096 KB Output is correct
9 Correct 199 ms 16060 KB Output is correct
10 Correct 189 ms 16148 KB Output is correct
11 Correct 169 ms 16056 KB Output is correct
12 Correct 182 ms 16104 KB Output is correct
13 Correct 206 ms 16060 KB Output is correct
14 Correct 182 ms 16096 KB Output is correct
15 Correct 173 ms 16116 KB Output is correct
16 Correct 192 ms 16060 KB Output is correct
17 Correct 174 ms 16052 KB Output is correct
18 Correct 169 ms 16064 KB Output is correct
19 Correct 198 ms 16036 KB Output is correct
20 Correct 179 ms 16020 KB Output is correct
21 Correct 167 ms 16064 KB Output is correct
22 Correct 177 ms 16380 KB Output is correct
23 Correct 188 ms 16388 KB Output is correct
24 Correct 176 ms 16436 KB Output is correct
25 Correct 211 ms 16500 KB Output is correct
26 Correct 186 ms 16476 KB Output is correct
27 Correct 186 ms 16452 KB Output is correct
28 Correct 185 ms 16496 KB Output is correct
29 Correct 179 ms 16412 KB Output is correct
30 Correct 173 ms 16440 KB Output is correct
31 Correct 173 ms 16504 KB Output is correct
32 Correct 188 ms 16376 KB Output is correct
33 Correct 179 ms 16428 KB Output is correct
34 Correct 180 ms 16488 KB Output is correct
35 Correct 219 ms 16452 KB Output is correct
36 Correct 173 ms 16388 KB Output is correct
37 Correct 172 ms 16472 KB Output is correct
38 Correct 173 ms 16376 KB Output is correct
39 Correct 185 ms 16468 KB Output is correct
40 Correct 189 ms 16432 KB Output is correct
41 Correct 175 ms 16404 KB Output is correct
42 Correct 176 ms 16504 KB Output is correct
43 Correct 240 ms 16552 KB Output is correct
44 Correct 216 ms 16568 KB Output is correct
45 Correct 215 ms 16608 KB Output is correct
46 Correct 231 ms 16572 KB Output is correct
47 Correct 222 ms 16628 KB Output is correct
48 Correct 219 ms 16520 KB Output is correct
49 Correct 221 ms 16584 KB Output is correct
50 Correct 241 ms 16532 KB Output is correct
51 Correct 219 ms 16544 KB Output is correct
52 Correct 208 ms 16628 KB Output is correct
53 Correct 240 ms 16616 KB Output is correct
54 Correct 212 ms 16532 KB Output is correct
55 Correct 253 ms 16532 KB Output is correct
56 Correct 221 ms 16632 KB Output is correct
57 Correct 223 ms 16504 KB Output is correct
58 Correct 222 ms 16604 KB Output is correct
59 Correct 227 ms 16596 KB Output is correct
60 Correct 220 ms 16512 KB Output is correct
61 Correct 238 ms 16520 KB Output is correct
62 Correct 225 ms 16520 KB Output is correct
63 Correct 221 ms 16628 KB Output is correct
64 Incorrect 218 ms 16760 KB Output isn't correct
65 Halted 0 ms 0 KB -