Submission #211491

#	Time	Username	Problem	Language	Result	Execution time	Memory
211491		Lawliet	Cubeword (CEOI19_cubeword)	C++17	100 / 100	487 ms	26628 KiB

cubeword

#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int MAXS = 10;
const int MAXL = 65;
const int MAXN = 100010;
const int MOD = 998244353;
 
int n;
 
int qtd[MAXL][MAXL][MAXS];
 
lli ans[MAXL][MAXL][MAXL][MAXS];
 
lli result;
 
vector< int > p;
 
set< string > s;
 
int conv(char a)
{
	if( 'a' <= a && a <= 'z' ) return a - 'a';
	if( 'A' <= a && a <= 'Z' ) return 'z' - 'a' + 1 + a - 'A';
	return 'z' - 'a' + 1 + 'Z' - 'A' + 1 +  a - '0';
}

int qtdPermutations()
{
	int ans = 24;
	int curFat = 1;
	int curNum = 1;

	for(int i = 1 ; i < 4 ; i++)
	{
		if( p[i] != p[i - 1] )
		{
			ans /= curFat;
			curNum = 0;
			curFat = 1;
		}

		curFat *= ++curNum;
	}

	ans /= curFat;

	return ans;
}
 
void backtracking(int i)
{
	if( i == 4 )
	{
		for(int sz = 3 ; sz <= 10 ; sz++)
		{
			lli t = qtdPermutations();
 
			t *= ans[ p[0] ][ p[1] ][ p[2] ][sz]; t %= MOD;
			t *= ans[ p[0] ][ p[1] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[0] ][ p[2] ][ p[3] ][sz]; t %= MOD;
			t *= ans[ p[1] ][ p[2] ][ p[3] ][sz]; t %= MOD;
 
			result += t;
			result %= MOD;
		}
 
		return;
	}

	int lim = 0;
	if( !p.empty() ) lim = p.back();
 
	for(int k = lim ; k <= conv( '9' ) ; k++)
	{
		p.push_back( k );
		backtracking( i + 1 );
		p.pop_back();
	}
}
 
int main()
{
	cin >> n;
 
	for(int i = 1 ; i <= n ; i++)
	{
		string t;
		cin >> t;
 
		s.insert( t );
		reverse( t.begin() , t.end() );
		s.insert( t );
	}
 
	for(auto it = s.begin() ; it != s.end() ; it++)
	{
		string curT = *it;
 
		int first = conv( curT[0] );
		int last = conv( curT.back() );
		int sz = curT.size();
 
		qtd[first][last][sz]++;
	}
 
	for(int a = 0 ; a <= conv( '9' ) ; a++)
	{
		for(int b = a ; b <= conv( '9' ) ; b++)
		{
			for(int c = b ; c <= conv( '9' ) ; c++)
			{
				for(int sz = 3 ; sz <= 10 ; sz++)
				{
					for(int k = 0 ; k <= conv( '9' ) ; k++)
					{
						lli aux = 1;
 
						aux *= qtd[a][k][sz];
						aux *= qtd[b][k][sz];
						aux *= qtd[c][k][sz];
 
						ans[a][b][c][sz] += aux;
						ans[a][b][c][sz] %= MOD;
					}
				}
			}
		}
	}
 
	backtracking( 0 );
 
	printf("%lld\n",result);
}

Compilation message (stderr)

cubeword.cpp: In function 'void backtracking(int)':
cubeword.cpp:61:6: warning: iteration 7 invokes undefined behavior [-Waggressive-loop-optimizations]
    t *= ans[ p[0] ][ p[1] ][ p[2] ][sz]; t %= MOD;
    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cubeword.cpp:57:23: note: within this loop
   for(int sz = 3 ; sz <= 10 ; sz++)
                    ~~~^~~~~

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