제출 #519048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519048		Monarchuwu	Cubeword (CEOI19_cubeword)	C++17	100 / 100	284 ms	38504 KiB

cubeword

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_set>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e5 + 9, mod = 998244353;
int n;
int a[11][62][62][2];

bool palind(string s) {
    int l(0), r(s.size() - 1);
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l, --r;
    }
    return true;
}

int num(char c) {
    if ('a' <= c && c <= 'z') return c - 'a';
    if ('A' <= c && c <= 'Z') return c - 'A' + 26;
    if ('0' <= c && c <= '9') return c - '0' + 52;
    return -1;
}

ll calc(int len, int i, int j) {
    if (i != j) {
        if (i > j) swap(i, j);
        return a[len][i][j][0];
    }
    return (a[len][i][j][1] + a[len][i][j][0] * 2) % mod;
}

ll perm[62][62][62][62], d[62][62][62];
void build_d(int len) {
    for (int i1 = 0; i1 < n; ++i1)
        for (int i2 = i1; i2 < n; ++i2)
            for (int i3 = i2; i3 < n; ++i3) {
                d[i1][i2][i3] = 0;
                for (int i = 0; i < n; ++i)
                    (d[i1][i2][i3] += calc(len, i, i1) * calc(len, i, i2) % mod * calc(len, i, i3)) %= mod;
            }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;

    unordered_set<string> S;
    vector<int> ch;
    for (int ii = 0; ii < n; ++ii) {
        string s; cin >> s;
        if (S.count(s)) continue;

        int i = num(s[0]), j = num(s.back());
        if (i > j) swap(i, j);
        ch.push_back(i);
        ch.push_back(j);

        ++a[s.size()][i][j][palind(s)];
        reverse(all(s));
        S.insert(s);
    }
    sort(all(ch));
    ch.resize(unique(all(ch)) - ch.begin());
    n = ch.size();

    for (int len = 3; len <= 10; ++len)
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j) {
                int i1 = ch[i], i2 = ch[j];
                a[len][i][j][0] = a[len][i1][i2][0];
                a[len][i][j][1] = a[len][i1][i2][1];
            }

    for (int i1 = 0; i1 < n; ++i1)
        for (int i2 = i1; i2 < n; ++i2)
            for (int i3 = i2; i3 < n; ++i3)
                for (int i4 = i3; i4 < n; ++i4) {
                    perm[i1][i2][i3][i4] = i1 == i4 ? 1 : i1 == i3 || i2 == i4 ? 4 : i1 == i2 && i3 == i4 ? 6 : i1 == i2 || i2 == i3 || i3 == i4 ? 12 : 24;
                }

    ll ans(0);
    for (int len = 3; len <= 10; ++len) {
        build_d(len);
        for (int i1 = 0; i1 < n; ++i1)
            for (int i2 = i1; i2 < n; ++i2)
                for (int i3 = i2; i3 < n; ++i3)
                    for (int i4 = i3; i4 < n; ++i4)
                        (ans += d[i1][i2][i3] * d[i1][i2][i4] % mod * d[i1][i3][i4] % mod * d[i2][i3][i4] % mod * perm[i1][i2][i3][i4]) %= mod;
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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