Submission #519365

#	Time	Username	Problem	Language	Result	Execution time	Memory
519365		sidon	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1034 ms	31516 KiB

cubeword

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define F(X, Y) for(X = 0; X < Y; 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[LIM][B][B][B], res;
map<string, bool> inp;
int i, j, k, l, x;

#define c(i, j, k, l) ((b[L][i][j][l] * b[L][j][k][l]) % M)
 
int32_t main() {
	cin >> n;
	while(n--) {
		string s; cin >> s;
		i = size(s);
 
		if(inp[s]) continue;
 
		string t = s;
		reverse(begin(t), end(t));
		inp[s] = inp[t] = 1;
 
		int z = get(s[0]), y = get(end(s)[-1]);
		++a[i-3][z][y];
		if(s != t) ++a[i-3][y][z];
	}
 
	for(int L = 0; L < LIM; L++) {
		F(i, B) F(j, i+1) F(k, j+1) F(x, B)
			b[L][i][j][k] += a[L][i][x] * a[L][j][x] * a[L][k][x];

		F(i, B) F(j, i+1) F(k, j+1) F(x, B)
			b[L][i][j][k] %= M;

		F(i, B) F(j, i+1) F(k, j+1) F(x, B)
			b[L][i][k][j] = b[L][j][i][k] = b[L][j][k][i] = b[L][k][i][j] = b[L][k][j][i] = b[L][i][j][k];

		F(i, B) F(j, B) F(k, B) F(l, B)
			res += (c(i, j, k, l) * c(l, k, j, i)) % M;
	}
 
	cout << res % M;
}

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