oj.uz

답안 #579186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579186 2022-06-18T12:49:18 Z tengiz05 Cubeword (CEOI19_cubeword) C++17
84 / 100
 940 ms 4384 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const string ex = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
};

constexpr int K = 45;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<string>> s(11);
    for (int i = 0; i < n; i++) {
        string g;
        cin >> g;
        string t(g.rbegin(), g.rend());
        if (t < g)
            g = t;
        s[g.size()].push_back(g);
    }
    
    auto work = [&](vector<string> &s) {
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        
        int n = s.size();
        Z cnt[K][K] {}, cntp[K][K] {};
        for (int i = 0; i < n; i++) {
            int x = ex.find(s[i][0]);
            int y = ex.find(s[i].back());
            string t(s[i].rbegin(), s[i].rend());
            if (s[i] == t) {
                cntp[x][y] += 1;
            } else {
                cnt[x][y] += 1;
                cnt[y][x] += 1;
            }
        }
        
        Z dp[K][K][K] {};
        
        for (int a = 0; a < K; a++) {
            for (int b = 0; b < K; b++) {
                for (int c = 0; c < K; c++) {
                    for (int x = 0; x < K; x++) {
                        Z res = 1;
                        res *= ((a == x) * cntp[a][x]) + cnt[a][x];
                        res *= ((b == x) * cntp[b][x]) + cnt[b][x];
                        res *= ((c == x) * cntp[c][x]) + cnt[c][x];
                        dp[a][b][c] += res;
                    }
                }
            }
        }
        
        Z ans = 0;
        
        for (int a = 0; a < K; a++) {
            for (int b = 0; b < K; b++) {
                for (int c = 0; c < K; c++) {
                    for (int d = 0; d < K; d++) {
                        ans += dp[a][b][c] * dp[a][c][d] * dp[a][b][d] * dp[b][c][d];
                    }
                }
            }
        }
        
        return ans;
    };
    
    Z ans = 0;
    for (int k = 3; k <= 10; k++) {
        ans += work(s[k]);
    }
    
    cout << ans.val() << "\n";
    
    return 0;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 749 ms 3984 KB Output is correct
2 Correct 709 ms 4140 KB Output is correct
3 Correct 760 ms 4196 KB Output is correct
4 Correct 723 ms 4140 KB Output is correct
5 Correct 698 ms 4016 KB Output is correct
6 Correct 723 ms 3976 KB Output is correct
7 Correct 700 ms 4184 KB Output is correct
8 Correct 699 ms 4020 KB Output is correct
9 Correct 703 ms 4016 KB Output is correct
10 Correct 727 ms 4056 KB Output is correct
11 Correct 706 ms 3948 KB Output is correct
12 Correct 718 ms 4172 KB Output is correct
13 Correct 689 ms 3968 KB Output is correct
14 Correct 718 ms 4304 KB Output is correct
15 Correct 709 ms 4180 KB Output is correct
16 Correct 728 ms 4020 KB Output is correct
17 Correct 692 ms 4184 KB Output is correct
18 Correct 713 ms 3988 KB Output is correct
19 Correct 707 ms 3936 KB Output is correct
20 Correct 704 ms 4060 KB Output is correct
21 Correct 709 ms 4044 KB Output is correct

Subtask #2
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 749 ms 3984 KB Output is correct
2 Correct 709 ms 4140 KB Output is correct
3 Correct 760 ms 4196 KB Output is correct
4 Correct 723 ms 4140 KB Output is correct
5 Correct 698 ms 4016 KB Output is correct
6 Correct 723 ms 3976 KB Output is correct
7 Correct 700 ms 4184 KB Output is correct
8 Correct 699 ms 4020 KB Output is correct
9 Correct 703 ms 4016 KB Output is correct
10 Correct 727 ms 4056 KB Output is correct
11 Correct 706 ms 3948 KB Output is correct
12 Correct 718 ms 4172 KB Output is correct
13 Correct 689 ms 3968 KB Output is correct
14 Correct 718 ms 4304 KB Output is correct
15 Correct 709 ms 4180 KB Output is correct
16 Correct 728 ms 4020 KB Output is correct
17 Correct 692 ms 4184 KB Output is correct
18 Correct 713 ms 3988 KB Output is correct
19 Correct 707 ms 3936 KB Output is correct
20 Correct 704 ms 4060 KB Output is correct
21 Correct 709 ms 4044 KB Output is correct
22 Correct 694 ms 4076 KB Output is correct
23 Correct 697 ms 4240 KB Output is correct
24 Correct 707 ms 3976 KB Output is correct
25 Correct 696 ms 4092 KB Output is correct
26 Correct 704 ms 4232 KB Output is correct
27 Correct 701 ms 4084 KB Output is correct
28 Correct 702 ms 4256 KB Output is correct
29 Correct 725 ms 4016 KB Output is correct
30 Correct 711 ms 4208 KB Output is correct
31 Correct 691 ms 4168 KB Output is correct
32 Correct 709 ms 4216 KB Output is correct
33 Correct 706 ms 4228 KB Output is correct
34 Correct 739 ms 3988 KB Output is correct
35 Correct 736 ms 4384 KB Output is correct
36 Correct 711 ms 4240 KB Output is correct
37 Correct 717 ms 4076 KB Output is correct
38 Correct 705 ms 3916 KB Output is correct
39 Correct 705 ms 3908 KB Output is correct
40 Correct 711 ms 4076 KB Output is correct
41 Correct 701 ms 3952 KB Output is correct
42 Correct 704 ms 4012 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 749 ms 3984 KB Output is correct
2 Correct 709 ms 4140 KB Output is correct
3 Correct 760 ms 4196 KB Output is correct
4 Correct 723 ms 4140 KB Output is correct
5 Correct 698 ms 4016 KB Output is correct
6 Correct 723 ms 3976 KB Output is correct
7 Correct 700 ms 4184 KB Output is correct
8 Correct 699 ms 4020 KB Output is correct
9 Correct 703 ms 4016 KB Output is correct
10 Correct 727 ms 4056 KB Output is correct
11 Correct 706 ms 3948 KB Output is correct
12 Correct 718 ms 4172 KB Output is correct
13 Correct 689 ms 3968 KB Output is correct
14 Correct 718 ms 4304 KB Output is correct
15 Correct 709 ms 4180 KB Output is correct
16 Correct 728 ms 4020 KB Output is correct
17 Correct 692 ms 4184 KB Output is correct
18 Correct 713 ms 3988 KB Output is correct
19 Correct 707 ms 3936 KB Output is correct
20 Correct 704 ms 4060 KB Output is correct
21 Correct 709 ms 4044 KB Output is correct
22 Correct 694 ms 4076 KB Output is correct
23 Correct 697 ms 4240 KB Output is correct
24 Correct 707 ms 3976 KB Output is correct
25 Correct 696 ms 4092 KB Output is correct
26 Correct 704 ms 4232 KB Output is correct
27 Correct 701 ms 4084 KB Output is correct
28 Correct 702 ms 4256 KB Output is correct
29 Correct 725 ms 4016 KB Output is correct
30 Correct 711 ms 4208 KB Output is correct
31 Correct 691 ms 4168 KB Output is correct
32 Correct 709 ms 4216 KB Output is correct
33 Correct 706 ms 4228 KB Output is correct
34 Correct 739 ms 3988 KB Output is correct
35 Correct 736 ms 4384 KB Output is correct
36 Correct 711 ms 4240 KB Output is correct
37 Correct 717 ms 4076 KB Output is correct
38 Correct 705 ms 3916 KB Output is correct
39 Correct 705 ms 3908 KB Output is correct
40 Correct 711 ms 4076 KB Output is correct
41 Correct 701 ms 3952 KB Output is correct
42 Correct 704 ms 4012 KB Output is correct
43 Correct 736 ms 3868 KB Output is correct
44 Correct 698 ms 4136 KB Output is correct
45 Correct 720 ms 4240 KB Output is correct
46 Correct 728 ms 4220 KB Output is correct
47 Correct 743 ms 3968 KB Output is correct
48 Correct 733 ms 4240 KB Output is correct
49 Correct 805 ms 4232 KB Output is correct
50 Correct 753 ms 4232 KB Output is correct
51 Correct 805 ms 4308 KB Output is correct
52 Correct 798 ms 3960 KB Output is correct
53 Correct 940 ms 3972 KB Output is correct
54 Correct 764 ms 4028 KB Output is correct
55 Correct 860 ms 4232 KB Output is correct
56 Correct 819 ms 4032 KB Output is correct
57 Correct 780 ms 3992 KB Output is correct
58 Correct 792 ms 4224 KB Output is correct
59 Correct 748 ms 3980 KB Output is correct
60 Correct 723 ms 3972 KB Output is correct
61 Correct 716 ms 3976 KB Output is correct
62 Correct 719 ms 4224 KB Output is correct
63 Correct 781 ms 3976 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 749 ms 3984 KB Output is correct
2 Correct 709 ms 4140 KB Output is correct
3 Correct 760 ms 4196 KB Output is correct
4 Correct 723 ms 4140 KB Output is correct
5 Correct 698 ms 4016 KB Output is correct
6 Correct 723 ms 3976 KB Output is correct
7 Correct 700 ms 4184 KB Output is correct
8 Correct 699 ms 4020 KB Output is correct
9 Correct 703 ms 4016 KB Output is correct
10 Correct 727 ms 4056 KB Output is correct
11 Correct 706 ms 3948 KB Output is correct
12 Correct 718 ms 4172 KB Output is correct
13 Correct 689 ms 3968 KB Output is correct
14 Correct 718 ms 4304 KB Output is correct
15 Correct 709 ms 4180 KB Output is correct
16 Correct 728 ms 4020 KB Output is correct
17 Correct 692 ms 4184 KB Output is correct
18 Correct 713 ms 3988 KB Output is correct
19 Correct 707 ms 3936 KB Output is correct
20 Correct 704 ms 4060 KB Output is correct
21 Correct 709 ms 4044 KB Output is correct
22 Correct 694 ms 4076 KB Output is correct
23 Correct 697 ms 4240 KB Output is correct
24 Correct 707 ms 3976 KB Output is correct
25 Correct 696 ms 4092 KB Output is correct
26 Correct 704 ms 4232 KB Output is correct
27 Correct 701 ms 4084 KB Output is correct
28 Correct 702 ms 4256 KB Output is correct
29 Correct 725 ms 4016 KB Output is correct
30 Correct 711 ms 4208 KB Output is correct
31 Correct 691 ms 4168 KB Output is correct
32 Correct 709 ms 4216 KB Output is correct
33 Correct 706 ms 4228 KB Output is correct
34 Correct 739 ms 3988 KB Output is correct
35 Correct 736 ms 4384 KB Output is correct
36 Correct 711 ms 4240 KB Output is correct
37 Correct 717 ms 4076 KB Output is correct
38 Correct 705 ms 3916 KB Output is correct
39 Correct 705 ms 3908 KB Output is correct
40 Correct 711 ms 4076 KB Output is correct
41 Correct 701 ms 3952 KB Output is correct
42 Correct 704 ms 4012 KB Output is correct
43 Correct 736 ms 3868 KB Output is correct
44 Correct 698 ms 4136 KB Output is correct
45 Correct 720 ms 4240 KB Output is correct
46 Correct 728 ms 4220 KB Output is correct
47 Correct 743 ms 3968 KB Output is correct
48 Correct 733 ms 4240 KB Output is correct
49 Correct 805 ms 4232 KB Output is correct
50 Correct 753 ms 4232 KB Output is correct
51 Correct 805 ms 4308 KB Output is correct
52 Correct 798 ms 3960 KB Output is correct
53 Correct 940 ms 3972 KB Output is correct
54 Correct 764 ms 4028 KB Output is correct
55 Correct 860 ms 4232 KB Output is correct
56 Correct 819 ms 4032 KB Output is correct
57 Correct 780 ms 3992 KB Output is correct
58 Correct 792 ms 4224 KB Output is correct
59 Correct 748 ms 3980 KB Output is correct
60 Correct 723 ms 3972 KB Output is correct
61 Correct 716 ms 3976 KB Output is correct
62 Correct 719 ms 4224 KB Output is correct
63 Correct 781 ms 3976 KB Output is correct
64 Incorrect 729 ms 4232 KB Output isn't correct
65 Halted 0 ms 0 KB -