Submission #786435

#	Time	Username	Problem	Language	Result	Execution time	Memory
786435		blue	Cubeword (CEOI19_cubeword)	C++17	84 / 100	247 ms	36208 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const ll mod = 998'244'353LL;

const int Z = 32;

int ad(ll a, ll b)
{
	return (a + b) % mod;
}

void selfadd(int& a, ll b)
{
	a = ad(a, b);
}

int mul(ll a, ll b)
{
	return (a * b) % mod;
}

int getnum(char c)
{
	// if('a' <= c && c <= 'z')
	// 	return c - 'a';
	// else if('A' <= c && c <= 'Z')
	// 	return 26 + c - 'A';
	// else if('0' <= c && c <= '9')
	// 	return 26 + 26 + c - '0';
	// else
	// 	assert(0);

	if('a' <= c && c <= 'z')
		return c - 'a';
	else
		return 16 + c - 'A';
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	set<string> words;

	for(int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;

		words.insert(s);

		reverse(s.begin(), s.end());

		words.insert(s);
	}

	vector<pii> wl[11];

	for(string w : words)
	{
		wl[sz(w)].push_back({getnum(w[0]), getnum(w.back())});
	}


// cerr << "done\n";

	int res = 0;

	for(int l = 3; l <= 10; l++)
	{
		// cerr << "l = " << l << '\n';
		vvi ct(Z, vi(Z, 0));

		for(pii z : wl[l])
		{
			ct[z.first][z.second]++;
		}

		vvvi ct3(Z, vvi(Z, vi(Z, 0)));

		for(int a = 0; a < Z; a++)
		{
			for(int b = 0; b < Z; b++)
			{
				for(int c = 0; c < Z; c++)
				{
					for(int x = 0; x < Z; x++)
					{
						selfadd(ct3[a][b][c], mul(ct[x][a], mul(ct[x][b], ct[x][c])));
					}
				}
			}
		}

		for(int a = 0; a < Z; a++)
		{
			for(int b = 0; b < Z; b++)
			{
				for(int c = 0; c < Z; c++)
				{
					for(int d = 0; d < Z; d++)
					{
						selfadd(res, mul(ct3[a][b][c], mul(ct3[b][c][d], mul(ct3[c][d][a], ct3[d][a][b]))));
					}
				}
			}
		}
	}

	cout << res << '\n';
}

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