Submission #314908

#	Time	Username	Problem	Language	Result	Execution time	Memory
314908		shivensinha4	Cubeword (CEOI19_cubeword)	C++17	21 / 100	1187 ms	33268 KiB

cubeword

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'

const int MXV = 16;
const ll mod = 998244353;
ll trans[MXV+1][MXV+1], ct[MXV+1][MXV+1][MXV+1][MXV+1], cts[MXV+1][MXV+1][MXV+1][MXV+1];
bool curr[MXV+1];

int getChar(char a) {
	//cout << a << " " << (a >= 'a' ? (a-'a') : (16+a-'A')) << endl;
	int v = a >= 'a' ? (a-'a') : (16+a-'A');
	assert(v <= MXV);
	return v;
}

ll mul(vector<ll> nums) {
	ll ans = nums[0];
	for_(i, 1, nums.size()) ans = (ans * nums[i]) % mod;
	return ans;
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<vector<vi>> words(11);
	vector<gp_hash_table<string, null_type>> raw(11);
	for_(i, 0, n) {
		string s; cin >> s;
		if (raw[s.size()].find(s) != raw[s.size()].end()) continue;
		int a = getChar(s[0]), b = getChar(s.back()), c;
		string temp = s;
		reverse(temp.begin(), temp.end());
		c = temp == s;
		words[s.size()].push_back({a, b, c});
		raw[s.size()].insert(s);
		if (!c) raw[s.size()].insert(temp);
	}
	
	ll ans = 0;
	for_(l, 3, 11) {
		if (!words[l].size()) continue;
		//cout << l << "-------" << endl;
		memset(trans, 0, sizeof(trans)); memset(ct, 0, sizeof(ct)); memset(ct, 0, sizeof(cts)); memset(curr, false, sizeof(curr));
		vi used;
		ll v;
		for (auto i: words[l]) {
			trans[i[0]][i[1]] += 1;
			if (!curr[i[0]]) used.push_back(i[0]);
			if (i[0] != i[1] and !curr[i[1]]) used.push_back(i[1]);
			curr[i[0]] = curr[i[1]] = true;
			if (!i[2]) trans[i[1]][i[0]] += 1;
		}
		for (int a: used) for (int b: used) for (int c: used) for (int d: used) {
			cts[a][b][c][d] = mul({trans[a][b], trans[b][c], trans[c][d], trans[d][a]});
			v = cts[a][b][c][d];
			if (!v) continue;
			
			for (int cc: used) for (int dd: used) {
				ct[a][b][cc][dd] += mul({v, trans[c][cc], trans[d][dd]});
				if (ct[a][b][cc][dd] >= mod) ct[a][b][cc][dd] -= mod;
			}
		}
		for (int a: used) for (int b: used) for (int c: used) for (int d: used) {
			if (!cts[a][b][c][d]) continue;
			for (int aa: used) for (int bb: used) {
				ans += mul({cts[a][b][c][d], ct[aa][bb][c][d], trans[a][aa], trans[b][bb]});
				if (ans >= mod) ans -= mod;
			}
		}
	}
	
	cout << ans << endl;
	

	return 0;
}

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