제출 #779853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779853		pedroslrey	Cubeword (CEOI19_cubeword)	C++17	100 / 100	793 ms	10176 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

const int ALPHA = 65;
const int MOD = 998244353;

int cnt[ALPHA][ALPHA];
lli prec[ALPHA][ALPHA][ALPHA];

int ctoord(char c) {
	if ('a' <= c && c <= 'z') return c - 'a';
	if ('A' <= c && c <= 'Z') return c - 'A' + 26;
	return 2*26 + c - '0';
}

lli solve(vector<string> &words) {
	if (words.empty()) return 0;
	for (int a = 0; a < ALPHA; ++a)
		for (int b = 0; b < ALPHA; ++b)
			for (int c = 0; c < ALPHA; ++c)
				prec[a][b][c] = 0;

	for (int a = 0; a < ALPHA; ++a)
		for (int b = 0; b < ALPHA; ++b)
			cnt[a][b] = 0;

	for (string w: words)
		++cnt[ctoord(w[0])][ctoord(w.back())];

	for (int a = 0; a < ALPHA; ++a)
		for (int b = a; b < ALPHA; ++b)
			for (int c = b; c < ALPHA; ++c) {
				for (int i = 0; i < ALPHA; ++i) {
					prec[a][b][c] += 1LL*cnt[a][i]*cnt[b][i]*cnt[c][i];
					prec[a][b][c] %= MOD;
				}
				//if (!words.empty() && a < 30 && b < 30 && c < 30) cerr << "prec " << (char)(a + 'a') << " " << (char)(b + 'a') << " " << (char)(c + 'a') << " " << prec[a][b][c] << "\n";
				prec[a][c][b] = prec[b][c][a] = prec[b][a][c] = prec[c][a][b] = prec[c][b][a] = prec[a][b][c];
			}

	lli ans = 0;
	for (int a = 0; a < ALPHA; ++a)
		for (int b = 0; b < ALPHA; ++b)
			for (int c = 0; c < ALPHA; ++c)
				for (int d = 0; d < ALPHA; ++d) 
					ans += prec[a][b][c]%MOD
						  *prec[a][b][d]%MOD
						  *prec[a][c][d]%MOD
						  *prec[b][c][d]%MOD;
	return ans;
}

int main() {
	int n;
	cin >> n;

	vector<vector<string>> words(11);
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;

		words[s.size()].push_back(s);
		reverse(s.begin(), s.end());
		words[s.size()].push_back(s);
	}

	lli ans = 0;
	for (auto &xs: words) {
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());

		ans += solve(xs);
		ans %= MOD;
	}

	cout << ans << "\n";
}

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