Submission #1233243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233243		djsksbrbf	Cubeword (CEOI19_cubeword)	C++20	100 / 100	800 ms	9388 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
const int MAX = 2e5 + 5;
const int MOD = 998244353;
#define int ll

vector <string> v[11];
int swit(char c){
	if(0 <= c - 'A' && c - 'A' < 26)return (c - 'A' + 1);
	else if(0 <= c - 'a' && c - 'a' < 26)return (c - 'a' + 27);
	return (c - '0' + 53);
}

ll ad(ll x, ll y){
	x %= MOD;
	y %= MOD;
	
	return (x + y) % MOD;
}

ll mul(ll x, ll y){
	x %= MOD;
	y %= MOD;
	
	return (x *y) % MOD;
}

int chek(int a, int b, int c, int d){
	if(a != b && b != c && c != d)return 24;
	if(a != b && b != c && c == d)return 12;
	if(a != b && b == c && c != d)return 12;
	if(a == b && b != c && c != d)return 12;
	if(a == b && b != c && c == d)return 6;
	if(a == b && b == c && c != d)return 4;
	if(a != b && b == c && c == d)return 4;
	return 1;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n; cin >> n;
	
	for(int i  =1 ; i <= n ; i++){
		string x; cin >> x;
		v[(int)x.size()].pb(x);
	}
	
	ll ans = 0;
	for(int len = 3 ; len <= 10 ; len++){
		set <string> can;
		ll cnt[70][70];memset(cnt, 0, sizeof(cnt));
		
		for(auto it : v[len]){
			can.insert(it);
			reverse(it.begin(), it.end());
			can.insert(it);
		}
		
		for(auto it : can)cnt[swit(it[0])][swit(it.back())]++;
		
		ll dp[70][70][70];
		for(int i = 1 ; i <= 62 ; i++){
			for(int j = 1 ; j <= 62 ; j++){
				for(int k = 1 ; k <= 62 ; k++){
					dp[i][j][k] = 0;
					for(int l = 1 ; l <= 62 ; l++){
						ll t = mul(cnt[i][l], mul(cnt[j][l], cnt[k][l]));
						dp[i][j][k] = ad(dp[i][j][k], t);
					}
				}
			}
		}
		
		ll tm = 0;
		for(int i = 1 ; i <= 62 ; i++){
			for(int j = i ; j <= 62 ; j++){
				for(int k = j ; k <= 62 ; k++){
					for(int l = k ; l <= 62 ; l++){
						ll tmp = mul(dp[i][j][k], mul(dp[i][j][l], mul(dp[i][k][l], dp[j][k][l])));
						
						tmp = mul(tmp, chek(i, j, k, l));
						tm = ad(tm, tmp);
					}
				}
			}
		}
		
		ans = ad(ans, tm);
	}
	cout << ans << endl;
	
	return 0;
}

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