Submission #519344

#	Time	Username	Problem	Language	Result	Execution time	Memory
519344		sidon	Cubeword (CEOI19_cubeword)	C++17	0 / 100	1185 ms	125752 KiB

cubeword

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define F(X) for(X = 0; X < B; X++)
 
const int B = 62, LIM = 8, M = 998244353;
 
int get(char c) {
	if(c < 60) return c - 48;
	return c - (c < 95 ? 55 : 61);
}
 
int n, _a[LIM][B][B], b[B][B][B], c[B][B][B][B], res;
map<string, bool> inp[11];
int i, j, k, l, x;
 
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	while(n--) {
		string s; cin >> s;
		if(get(s[0]) > get(end(s)[-1]))
			reverse(begin(s), end(s));
		i = size(s);
 
		if(inp[i][s]) continue;
		inp[i][s] = 1;
 
		string t = s;
		reverse(begin(t), end(t));
 
		int x = get(s[0]), y = get(end(s)[-1]);
		++_a[i-3][x][y];
		if(s != t) ++_a[i-3][y][x];
	}
 
	for(int L = 0; L < 8; L++) {
		auto a = _a[L];
		memset(b, 0, sizeof b);
		memset(c, 0, sizeof c);
 
		F(i) F(j) F(k) F(x)
			b[i][j][k] += (a[i][x] * a[j][x] * a[k][x]) % M;
 
		F(i) F(j) F(k) F(l) {
			if((c[i][j][k][l] = (b[i][j][l] * b[j][k][l])) >= M)
				c[i][j][k][l] %= M;
		}
		
		F(i) F(j) F(k) F(l) {
			(res += c[i][j][k][l] * c[l][k][j][i]);
			if(res >= M) res %= M;
		}
	}
 
	cout << res;
}

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