Submission #1231331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231331		radodododo	Cubeword (CEOI19_cubeword)	C++20	84 / 100	594 ms	8492 KiB

cubeword

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>

using namespace std;

vector<vector<long long>> mp;

int main() {
	//cout << (long long)'a' - 'A' << " " << (long long)'z' - 'A' << '\n' << (long long)'A' - 'A' << " " << (long long)'Z' - 'A';
	long long mod = 998244353;
	long long n;
	cin >> n;
	vector<vector<string>> have(11);
	for (long long i = 0; i < n; i++) {
		string s;
		cin >> s;
		have[s.size()].push_back(s);
	}
	long long ans = 0;
	for (long long len = 3; len <= 10; len++) {
		mp.assign(58, vector<long long>(58, 0));
		vector<vector<set<string>>> pupu(58, vector<set<string>>(58));
		for (auto s : have[len]) {
			/*if (s[0] != s.back()) {
				mp[min(s[0], s.back()) - 'A'][max(s[0], s.back()) - 'A']++;
				mp[max(s[0], s.back()) - 'A'][min(s[0], s.back()) - 'A']++;
				mp[min(s[0], s.back()) - 'A'][max(s[0], s.back()) - 'A'] %= mod;
				mp[max(s[0], s.back()) - 'A'][min(s[0], s.back()) - 'A'] %= mod;
			}
			else {
				bool palind = 1;
				for (long long i = 0; i < s.size(); i++) {
					if (s[i] != s[s.size() - 1 - i]) {
						palind = 0;
						break;
					}
				}
				if (palind) {
					mp[s[0] - 'A'][s[0] - 'A']++;
					mp[s[0] - 'A'][s[0] - 'A'] %= mod;
				}
				else {
					mp[s[0] - 'A'][s[0] - 'A'] += 2;
					mp[s[0] - 'A'][s[0] - 'A'] %= mod;
				}
			}*/
			pupu[s[0] - 'A'][s.back() - 'A'].insert(s);
			reverse(s.begin(), s.end());
			pupu[s[0] - 'A'][s.back() - 'A'].insert(s);
		}
		for (long long a = 0; a < 58; a++) {
			for (long long b = 0; b < 58; b++) {
				mp[a][b] = pupu[a][b].size();
			}
		}
		vector<vector<vector<long long>>> muls(58, vector<vector<long long>>(58, vector<long long>(58, 0)));
		for (long long a = 0; a < 58; a++) {
			if (a == 26) {
				a = 32;
			}
			for (long long b = 0; b < 58; b++) {
				if (b == 26) {
					b = 32;
				}
				for (long long c = 0; c < 58; c++) {
					if (c == 26) {
						c = 32;
					}
					for (long long x = 0; x < 58; x++) {
						muls[a][b][c] += (((mp[a][x] * mp[b][x]) % mod) * mp[c][x]) % mod;
						muls[a][b][c] %= mod;
					}
				}
			}
		}
		for (long long a = 0; a < 58; a++) {
			if (a == 26) {
				a = 32;
			}
			for (long long b = 0; b < 58; b++) {
				if (b == 26) {
					b = 32;
				}
				for (long long c = 0; c < 58; c++) {
					if (c == 26) {
						c = 32;
					}
					for (long long d = 0; d < 58; d++) {
						if (d == 26) {
							d = 32;
						}
						ans += (((((muls[a][b][c] * muls[a][b][d]) % mod) * muls[a][c][d]) % mod) * muls[b][c][d]) % mod;
						ans %= mod;
					}
				}
			}
		}
	}
	cout << ans;
}

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