Submission #223103

#	Time	Username	Problem	Language	Result	Execution time	Memory
223103		ryansee	Cubeword (CEOI19_cubeword)	C++14	100 / 100	1095 ms	20896 KiB

cubeword

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(int i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll n,mod=998244353,dp[62][62][62];
ll e[62][62];
vector<string> A[11];
unordered_map<string,bool> mp;
ll d(char ch){
	if(ch>='a'&&ch<='z') return ch-'a';
	else if(ch>='A'&&ch<='Z') return ch-'A'+26;
	else return 52+ch-'0';
}
// 0...61
int main(){
	FAST
	cin>>n;
	FOR(i,1,n){
		string a;cin>>a;
		A[a.size()].pb(a);
		// for(auto i:a) assert((i>='a'&&i<='p')||(i>='A'&&i<='P'));
	}
	ll sum=0;
	FOR(l,3,10){
		vector<string> v;
		FOR(i,0,siz(A[l])-1){
			reverse(all(A[l][i]));
			if(mp[A[l][i]])continue;
			reverse(all(A[l][i]));
			mp[A[l][i]]=1;
			v.pb(A[l][i]);
		}
		A[l]=v;
		mmst(e,0),mmst(dp,0);
		ll ans=0;
		auto ispalin=[&](string s){
			string tmp=s;
			reverse(all(tmp));
			return tmp==s;
		};
		for(auto i:A[l]){
			++ e[d(i[0])][d(i.back())];
			++ e[d(i.back())][d(i[0])];
			if(ispalin(i)) --e[d(i[0])][d(i[0])];
		}
		FOR(i,0,61)FOR(j,0,i)FOR(k,0,j)FOR(t,0,61){
			dp[i][j][k]+=e[t][i]*e[t][j]*e[t][k]%mod,dp[i][j][k]%=mod;
		}
		FOR(i,0,61)FOR(j,0,i)FOR(k,0,j)FOR(l,0,k){
			// ll a=0,b=0,c=0,d=0;
			// FOR(t,0,61){
				// a+=e[t][i]*e[t][j]*e[t][k]%mod,a%=mod;
				// b+=e[t][i]*e[t][j]*e[t][l]%mod,b%=mod;
				// c+=e[t][i]*e[t][k]*e[t][l]%mod,c%=mod;
				// d+=e[t][j]*e[t][k]*e[t][l]%mod,d%=mod;
			// }
			auto p=[&](ll a,ll b,ll c,ll d){
				vector<pi> v;
				v.eb(1, a);
				if(b==a) ++v[0].f; else v.eb(1,b);
				if(c==a) ++ v[0].f; else if(c==b) ++ v[1].f; else v.eb(1,c);
				if(d==a) ++ v[0].f; else if(d==b) ++ v[1].f; else if(a==b&&c==d) ++ v[1].f; else if(c==d) ++ v[2].f; else v.eb(1,d);
				if(siz(v)==4) return 4*3*2;
				else if(siz(v)==3) return 4*3;
				else if(siz(v)==2&&v[0].f==2) return 6; // 2 2
				else if(siz(v)==2) return 4;
				else return 1;
			};
			ans+=dp[i][j][k]*dp[i][j][l]%mod*dp[i][k][l]%mod*dp[j][k][l]%mod*p(i,j,k,l),ans%=mod;
		}
		sum+=ans,sum%=mod;
	}
	cout<<sum<<'\n';
} //
/*
1
badab

1
aoboc

2
FLOC
COLF

3
baobab
baboab
bob

3
OFDING
LFBMIO
ACCEPO

3
MANBLA
MANCOE
ANDNAE

*/

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