Submission #314883

#	Time	Username	Problem	Language	Result	Execution time	Memory
314883		shivensinha4	Cubeword (CEOI19_cubeword)	C++17	0 / 100	1188 ms	20116 KiB

cubeword

#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 = 10;
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];

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

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<set<string>> raw(11);
	for_(i, 0, n) {
		string s; cin >> s;
		if (raw[s.size()].count(s)) 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));
		ll v;
		for (auto i: words[l]) {
			trans[i[0]][i[1]] += 1;
			if (!i[2]) trans[i[1]][i[0]] += 1;
		}
		for_(a, 0, MXV+1) for_(b, 0, MXV+1) for_(c, 0, MXV+1) for_(d, 0, MXV+1) {
			cts[a][b][c][d] = mul({trans[a][b], trans[b][c], trans[c][d], trans[d][a]});
			//cout << (char) ('a'+a) << " " << (char) ('a'+b) << " " << (char) ('a'+c) << " " << (char) ('a'+d) << " " << cts[a][b][c][d] << endl;
			v = cts[a][b][c][d];
			for_(cc, 0, MXV+1) for_(dd, 0, MXV+1) {
				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_(a, 0, MXV+1) for_(b, 0, MXV+1) for_(c, 0, MXV+1) for_(d, 0, MXV+1) {
			for_(aa, 0, MXV+1) for_(bb, 0, MXV+1) 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: 0 / 21
• Subtask 2: 0 / 29
• Subtask 3: 0 / 34
• Subtask 4: 0 / 16