제출 #1168452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168452		SG2Alok	Cubeword (CEOI19_cubeword)	C++20	0 / 100	1102 ms	17036 KiB

cubeword

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
#define endl '\n'
#define hitaf ios_base::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
 
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>;
 
const ll MOD1 = 1e9 + 7;
const ll MOD = 998244353;
const ll INF = 4500000000000000000LL;
const ll mod1 = 6900000469;
const ll mod2 = 698000002369;
const int N = 62;
 
int n, m, q, a[1200005], b[500005], c[500005];
string s, s1, s2;
ll cnt[15][65][65];

int trn(char c){
	if(c >= 'a' && c <= 'z') return c - 'a';
	if(c >= 'A' && c <= 'Z') return c - 'A' + 26;
	return c - '0' + 52;
}

int main(){
	hitaf
	int T = 1;
//	cin >> T;
	
	while(T--){
		cin >> n;
		
		set<string> st;
		for(int i = 1; i <= n; i++){
			cin >> s;
			
			st.insert(s);
			string cur = s;
			reverse(cur.begin(), cur.end());
			st.insert(cur);
		}
		
		for(auto x: st){
			cnt[x.length()][trn(x[0])][trn(x.back())]++;
		}
		
		ll prob = 0;
		for(int len = 3; len <= 10; len++){
			vector<vector<vector<ll>>> prod(62, vector<vector<ll>>(62, vector<ll>(62, 0)));
			
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					for(int k = 0; k < N; k++){
						for(int l = 0; l < N; l++){
							prod[i][j][k] += cnt[len][i][l] * cnt[len][j][l] % MOD * cnt[len][k][l] % MOD;
							prod[i][j][k] %= MOD;
						}
					}
				}
			}
//			
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					for(int k = 0; k < N; k++){
						for(int l = 0; l < N; l++){
							prob += (((prod[i][j][k] * prod[j][k][l] % MOD) * prod[k][l][i]) % MOD * prod[l][i][j]) % MOD;
							prob %= MOD;
						}
					}
				}
			}
		}
		
		cout << prob << endl;
	}
	
	return 0;
}


/*
	
	dp[i][j] = 
*/

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