제출 #1231345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231345		radodododo	Cubeword (CEOI19_cubeword)	C++20	100 / 100	1044 ms	8912 KiB

cubeword

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

using namespace std;

vector<vector<long long>> mp;

long long chisl(char a) {
	if (a <= '9') {
		return a - '0';
	}
	if (a <= 'Z') {
		return a - 'A' + 10;
	}
	return a - 'a' + 36;
}

int main() {
	//cout << (long long)'a' - '0' << " " << (long long)'z' - '0' << '\n' << (long long)'A' - '0' << " " << (long long)'Z' - '0';
	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(62, vector<long long>(62, 0));
		vector<vector<set<string>>> pupu(62, vector<set<string>>(62));
		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[chisl(s[0])][chisl(s.back())].insert(s);
			reverse(s.begin(), s.end());
			pupu[chisl(s[0])][chisl(s.back())].insert(s);
		}
		for (long long a = 0; a < 62; a++) {
			for (long long b = 0; b < 62; b++) {
				mp[a][b] = pupu[a][b].size();
			}
		}
		vector<vector<vector<long long>>> muls(62, vector<vector<long long>>(62, vector<long long>(62, 0)));
		for (long long a = 0; a < 62; a++) {
			for (long long b = 0; b < 62; b++) {
				for (long long c = 0; c < 62; c++) {
					for (long long x = 0; x < 62; 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 < 62; a++) {
			for (long long b = 0; b < 62; b++) {
				for (long long c = 0; c < 62; c++) {
					for (long long d = 0; d < 62; d++) {
						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: 16 / 16