Submission #821889

#	Time	Username	Problem	Language	Result	Execution time	Memory
821889		NK_	Cubeword (CEOI19_cubeword)	C++17	100 / 100	365 ms	8712 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int MOD = 998244353;
using ll = int;
using str = string;

template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<V<str>> A(11);
	for(int i = 0; i < N; i++) {
		str s; cin >> s;
		A[size(s)].push_back(s);
		reverse(begin(s), end(s));
		A[size(s)].push_back(s);
	}

	auto TO = [&](const char &c) {
		if (islower(c)) return c - 'a';
		if (isupper(c)) return c - 'A' + 26;
		if (isdigit(c)) return c - '0' + 52;
		return -1;
	};

	const int C = 62;

	V<ll> fact = {1, 1, 2, 6, 24};

	ll ans = 0;
	for(int l = 3; l <= 10; l++) {

		sort(begin(A[l]), end(A[l]));
		A[l].erase(unique(begin(A[l]), end(A[l])), end(A[l]));

		V<V<ll>> CNT(C, V<ll>(C));

		for(auto s : A[l]) CNT[TO(s.front())][TO(s.back())]++;

		V<V<V<ll>>> ways(C, V<V<ll>>(C, V<ll>(C)));

		for(int a = 0; a < C; a++) for(int b = 0; b < C; b++) if (CNT[a][b] != 0) {
			for(int c = b; c < C; c++) if (CNT[a][c] != 0) {
				for(int d = c; d < C; d++) if (CNT[a][d] != 0) {
					ll way = (((CNT[a][b] * 1LL * CNT[a][c]) % MOD) * 1LL * CNT[a][d]) % MOD;
					
					ways[b][c][d] += way; 
					if (ways[b][c][d] >= MOD) ways[b][c][d] -= MOD;
				}
			}
		}

		vector<int> v;
		vector<int> amt(C);

		for(int a = 0; a < C; a++) for(int b = a; b < C; b++) for(int c = b; c < C; c++) {
			if (ways[a][b][c] == 0) continue;
			for(int d = c; d < C; d++) if (min(ways[a][b][d], min(ways[a][c][d], ways[b][c][d])) != 0) {
				ll way = ((ways[a][b][c] * 1LL * ways[a][b][d]) % MOD) * 1LL * ((ways[a][c][d] * 1LL * ways[b][c][d]) % MOD) % MOD;

				

				ll res = fact[4];
				v = {a, b, c, d}; 
				for(const auto &x : v) amt[x]++;
				for(const auto &x : v) {
					res /= fact[amt[x]];
					amt[x] = 0;
				}

				ans += (way * 1LL * res) % MOD;
				if (ans >= MOD) ans -= MOD;
			}
		}

	}

	cout << ans << nl;

    return 0;
}

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