Submission #1220866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220866		MateiKing80	Cubeword (CEOI19_cubeword)	C++20	100 / 100	168 ms	8564 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int mod = 998244353;
const int sigma = 62;

int toInt(char ch) {
	if ('a' <= ch && ch <= 'z')
		return ch - 'a';
	if ('A' <= ch && ch <= 'Z')
		return 26 + ch - 'A';
	return 52 + ch - '0';
}

int nrPerm(int a, int b, int c, int d) { //de facut permutari cu repetitii
	if (a == b && b == c && c == d)
		return 1;
	if (a == b && b == c)
		return 4;
	if (b == c && c == d)
		return 4;
	if (a == b && c == d)
		return 6;
	if (a == b || b == c || c == d)
		return 12;
	return 24;
}

int solve(vector<string> v) {
	if (v.empty())
		return 0;
	vector<string> nv;
	for (auto i : v) {
		nv.push_back(i);
		reverse(i.begin(), i.end());
		nv.push_back(i);
	}
	sort(nv.begin(), nv.end());
	v.clear();
	for (int i = 0; i < (int)nv.size(); i ++)
		if (!i || nv[i] != nv[i - 1])
			v.push_back(nv[i]);
	vector<vector<int>> nr(sigma, vector<int>(sigma, 0));
	for (auto i : v)
		nr[toInt(i[0])][toInt(i.back())] ++;
	vector<vector<vector<int>>> dp(sigma, vector<vector<int>>(sigma, vector<int>(sigma, 0)));
	for (int a = 0; a < sigma; a ++)
		for (int b = a; b < sigma; b ++)
			for (int c = b; c < sigma; c ++)
				for (int d = 0; d < sigma; d ++) {
					dp[a][b][c] += nr[a][d] * nr[b][d] % mod * nr[c][d] % mod;
					dp[a][b][c] %= mod;
				}
	int ans = 0;
	for (int a = 0; a < sigma; a ++)
		for (int b = a; b < sigma; b ++)
			for (int c = b; c < sigma; c ++)
				for (int d = c; d < sigma; d ++) {
					ans += nrPerm(a, b, c, d) * dp[a][b][c] % mod * dp[a][b][d] % mod * dp[a][c][d] % mod * dp[b][c][d] % mod;
					ans %= mod;
				}
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<vector<string>> v(11);
	for (int i = 0; i < n; i ++) {
		string s;
		cin >> s;
		v[(int)s.size()].push_back(s);
	}
	int ans = 0;
	for (int i = 3; i <= 10; i ++)
		ans += solve(v[i]), ans %= mod;
	cout << ans << '\n';
}

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