Submission #375021

#	Time	Username	Problem	Language	Result	Execution time	Memory
375021		ogibogi2004	Cubeword (CEOI19_cubeword)	C++14	50 / 100	171 ms	10504 KiB

cubeword

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXK=26;
const int MAXN=1e5+6;
map<char,int>mp;
const ll mod=998244353;
string s[MAXN];
int cnt[100][100];
int ans=0,n;
int dp[100][100][100];
void solve(int d)
{
	memset(cnt,0,sizeof(cnt));
	memset(dp,0,sizeof(dp));
	set<string>used;
	for(int i=0;i<n;i++)
	{
		if(s[i].size()!=d)continue;
		if(used.find(s[i])==used.end())
		{
			used.insert(s[i]);
			cnt[mp[s[i][0]]][mp[s[i][s[i].size()-1]]]++;
		}
		reverse(s[i].begin(),s[i].end());
		if(used.find(s[i])==used.end())
		{
			used.insert(s[i]);
			cnt[mp[s[i][0]]][mp[s[i][s[i].size()-1]]]++;
		}
		reverse(s[i].begin(),s[i].end());
	}
	if(used.size()==0)return;
	//cout<<d<<endl;
	for(int i1=1;i1<=MAXK;i1++)
	{
		for(int i2=1;i2<=MAXK;i2++)
		{
			for(int i3=1;i3<=MAXK;i3++)
			{
				if(i2<i1||i3<i1||i3<i2)
				{
					int mn=min(i1,min(i2,i3));
					int mx=max(i1,max(i2,i3));
					dp[i1][i2][i3]=dp[mn][i1+i2+i3-mn-mx][mx];
				}
				else 
				{
					for(int j=1;j<=MAXK;j++)
					{
						dp[i1][i2][i3]=dp[i1][i2][i3]+((ll)((ll)cnt[j][i1]*cnt[j][i2])%mod*cnt[j][i3])%mod;
						dp[i1][i2][i3]%=mod;
					}
				}
			}
		}
	}
	for(int i1=1;i1<=MAXK;i1++)
	{
		for(int i2=i1;i2<=MAXK;i2++)
		{
			for(int i3=i2;i3<=MAXK;i3++)
			{
				for(int i4=i3;i4<=MAXK;i4++)
				{
					ll c;
					if(i1==i2)
					{
						if(i2==i3)
						{
							if(i3==i4)c=1;
							else c=4;
						}
						else 
						{
							if(i3==i4)c=6;
							else c=12;
						}
					}
					else 
					{
						if(i2==i3)
						{
							if(i3==i4)c=4;
							else c=12;
						}
						else
						{
							if(i3==i4)c=12;
							else c=24;
						}
					}
					ans=ans+((ll)c*(((ll)(((ll)(((ll)dp[i1][i2][i3]*dp[i1][i2][i4])%mod)*dp[i1][i3][i4])%mod)*dp[i2][i3][i4])%mod))%mod;
					ans%=mod;
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for(char c='a';c<='z';c++)mp[c]=c-'a'+1;
	for(char c='A';c<='Z';c++)mp[c]=c-'A'+27;
	for(char c='0';c<='9';c++)mp[c]=c-'a'+43;
	cin>>n;
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=3;i<=10;i++)
	{
		solve(i);
	}
	cout<<ans<<endl;
return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'void solve(int)':
cubeword.cpp:19:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |   if(s[i].size()!=d)continue;
      |      ~~~~~~~~~~~^~~

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