Submission #447089

#	Time	Username	Problem	Language	Result	Execution time	Memory
447089		8e7	Cubeword (CEOI19_cubeword)	C++17	100 / 100	293 ms	16768 KiB

cubeword

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_set>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 200005
#define maxc 62
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
unordered_set<string> se[11];
ll val[maxc][maxc][maxc];
ll cnt[maxc][maxc];
char f(char c) {
	if (c >= '0' && c <= '9') return c;
   	if (c >= 'a' && c <= 'z') return char('0' + 36 + (c - 'a'));
	return char ('0' + 10 + (c - 'A'));	
}
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		for (auto &c:s) c = f(c);
		string t = s;
		reverse(t.begin(), t.end());
		se[s.size()].insert(s);
		if (t != s) se[s.size()].insert(t);
	}
	ll ans = 0;
	for (int siz = 3;siz <= 10;siz++) {
		for (int i = 0;i < maxc;i++) {
			for (int j = 0;j < maxc;j++) {
				cnt[i][j] = 0;
			}
		}
		for (auto s:se[siz]) {
			cnt[s[0] - '0'][s.back() - '0']++;
		}
		for (int i = 0;i < maxc;i++) {
			for (int j = i;j < maxc;j++) {
				for (int k = j;k < maxc;k++) {
					val[i][j][k] = 0;
					for (int l = 0;l < maxc;l++) {
						val[i][j][k] = (val[i][j][k] + cnt[i][l] * cnt[j][l] % mod * cnt[k][l]) % mod;
					}	
				}
			}
		}
		for (int i = 0;i < maxc;i++) {
			for (int j = i;j < maxc;j++) {
				for (int k = j;k < maxc;k++) {
					for (int l = k;l < maxc;l++) {
						ll x = (val[i][j][k] * val[i][j][l] % mod * val[i][k][l] % mod * val[j][k][l]) % mod; 
						int mult = 24;
						if (i == j) {
							if (j == k) mult = k == l ? 1 : 4;
							else mult = k == l ? 6 : 12;
						} else {
							if (j == k) mult = k == l ? 4 : 12;
							else mult = k == l ? 12 : 24;
						}
						ans = (ans + x * mult) % mod;
					}
				}
			}
		}
	}
	cout << ans << endl;
}

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