Submission #1039497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039497		Edu175	Cubeword (CEOI19_cubeword)	C++17	0 / 100	62 ms	7544 KiB

cubeword

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,isudgh=b;i<isudgh;i++)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto jhglkdfjg:v)cout<<jhglkdfjg<<" ";cout<<"\n";}
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef int ll;
typedef long long LL;
typedef pair<ll,ll> ii;
// #pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
const ll MOD=998244353,MAXA=62;

ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(LL a, LL b){return a*b%MOD;}
int fpow(int a, ll b){
	int r=1;
	while(b){if(b&1)r=mul(r,a); b>>=1; a=mul(a,a);}
	return r;
}

ll A; //alphabet
ll q[62][62];

ll solve(vector<string>&a){
	if(!SZ(a))return 0;
	// cout<<"solve "; imp(a);
	ll n=SZ(a);
	vector<char>c;
	fore(i,0,n)c.pb(a[i][0]),c.pb(a[i].back());
	sort(ALL(c));
	vector<char> ci;
	fore(i,0,SZ(c))if(!i||c[i]!=c[i-1])ci.pb(c[i]);
	c=ci;
	for(auto &s:a){
		auto change=[&](char &j){
			ll p=lower_bound(ALL(c),j)-c.begin();
			j=p;
		};
		change(s[0]); change(s.back());
	}
	// imp(a);
	A=SZ(c);
	set<string> st[A][A];
	for(auto s:a){
		st[int(s[0])][int(s.back())].insert(s);
		reverse(ALL(s));
		st[int(s[0])][int(s.back())].insert(s);
	}
	fore(i,0,A)fore(j,0,A)q[i][j]=SZ(st[i][j]);
	/*fore(i,0,A){
		imp(q[i]);
	}*/
	vector<ll>pot(5);
	pot[0]=1;
	fore(i,1,5)pot[i]=pot[i-1]*A;
	
	vector<ll>num(pot[3]);
	fore(mk,0,pot[3]){
		vector<ll>a(3);
		ll mki=mk;
		fore(i,0,3)a[i]=mki%A,mki/=A;
		fore(c,0,A){
			ll val=1;
			fore(j,0,3)val=mul(val,q[a[j]][c]);
			num[mk]=add(num[mk],val);
		}
	}
	ll ans=0;
	fore(mk,0,pot[4]){	
		
		ll res=1,m=mk%pot[3];
		fore(i,0,4){
			res=mul(res,num[m]);
			m=(m+(m%A*pot[3]))/A;
		}
		ans=add(ans,res);
		// imp(a);
		// imp(num);
		// cout<<": "<<res<<"\n\n";
	}
	return ans;
	
}
const ll MAXV=11;
int main(){FIN;
	ll n; cin>>n;
	vector<string> b[MAXV];
	fore(i,0,n){
		string s;cin>>s;
		b[SZ(s)].pb(s);
	}
	ll res=0;
	fore(i,0,MAXV){
		res=add(res,solve(b[i]));
	}
	// res=solve(b[5]);
	cout<<res<<"\n";
	return 0;
}

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