Submission #786467

#	Time	Username	Problem	Language	Result	Execution time	Memory
786467		blue	Cubeword (CEOI19_cubeword)	C++17	100 / 100	287 ms	19488 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 = 62;

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++)
	{
		int cr;
		// 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 = a; b < Z; b++)
			{
				for(int c = b; 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])));
					}
				}
			}
		}

		//1 unique value
		for(int a = 0; a < Z; a++)
			selfadd(res, mul(ct3[a][a][a], mul(ct3[a][a][a], mul(ct3[a][a][a], ct3[a][a][a]))));




		//2 unique values, 2 + 2

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





		//2 unique values, 1 + 3
		cr = 0;
		for(int a = 0; a < Z; a++)
		{
			for(int b = a+1; b < Z; b++)
			{
				selfadd(cr, mul(ct3[a][a][a], mul(ct3[a][a][b], mul(ct3[a][a][b], ct3[a][a][b]))));
				selfadd(cr, mul(ct3[b][b][b], mul(ct3[a][b][b], mul(ct3[a][b][b], ct3[a][b][b]))));
			}
		}
		selfadd(res, mul(cr, 4));





		//3 unique values

		cr = 0;

		for(int a = 0; a < Z; a++)
		{
			for(int b = a+1; b < Z; b++)
			{
				for(int c = b+1; c < Z; c++)
				{
					//1 + 1 + 2

					selfadd(cr, mul(ct3[a][b][c], mul(ct3[a][b][c], mul(ct3[a][c][c], ct3[b][c][c]))));
					selfadd(cr, mul(ct3[a][b][c], mul(ct3[a][b][c], mul(ct3[a][a][c], ct3[a][a][b]))));
					selfadd(cr, mul(ct3[a][b][c], mul(ct3[a][b][c], mul(ct3[a][b][b], ct3[b][b][c]))));
				}
			}
		}

		selfadd(res, mul(12, cr));





		//4 unique values

		cr = 0;

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

		selfadd(res, mul(cr, 24));

		// cerr << l << " : " << res << '\n';
	}

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

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