Submission #1276839

#TimeUsernameProblemLanguageResultExecution timeMemory
1276839Davdav1232Cubeword (CEOI19_cubeword)C++20
100 / 100
316 ms12084 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef __int128_t lll; ll MOD=998244353; int main(){ int n; cin>>n; lll num=62; vector<vector<vector<ll>>> words(8, vector<vector<ll>>(num, vector<ll>(num, 0))); map<char, ll> l; for(ll i='a'-'a'; i<='z'-'a'; i++){ l[(i+'a')]=i; } for(ll i='A'-'A'; i<='Z'-'A'; i++){ l[i+'A']=i+26; } l['0']=52; l['1']=53; l['2']=54; l['3']=55; l['4']=56; l['5']=57; l['6']=58; l['7']=59; l['8']=60; l['9']=61; set<ll> ss; for(int i=0; i<n; i++){ string s; cin>>s; ll a_s=0; ll curr_num=1; for(int i=0; i<s.size(); i++){ a_s+=curr_num * (l[s[i]]+1); curr_num*=(num+1); } bool e = ss.insert(a_s).second; if(e) words[s.size()-3][l[s[0]]][l[s[s.size()-1]]]++; reverse(s.begin(), s.end()); a_s=0; curr_num=1; for(int i=0; i<s.size(); i++){ a_s+=curr_num * (l[s[i]]+1); curr_num*=(num+1); } e = ss.insert(a_s).second; if(e) words[s.size()-3][l[s[0]]][l[s[s.size()-1]]]++; } ll ans=0; vector<ll> fact(5); fact[0]=1; fact[1]=1; fact[2]=2; fact[3]=6; fact[4]=24; for(int i=0; i<8; i++){ //ok now choose 4 letters vector<vector<vector<ll>>> e(num, vector<vector<ll>> (num, vector<ll> (num, 0))); for(int a=0; a<num; a++){ for(int b=a; b<num; b++){ for(int c=b; c<num; c++){ for(int d=0; d<num; d++){ e[a][b][c]+=words[i][a][d]*words[i][b][d]*words[i][c][d]; e[a][b][c]%=MOD; } } } } for(int a=0; a<num; a++){ for(int b=a; b<num; b++){ for(int c=b; c<num; c++){ for(int d=c; d<num; d++){ ll mul = 24; if (a == d) mul = 1; else if (a == c || b == d) mul = 4; else if (a == b && c == d) mul = 6; else if (a == b || b == c || c == d) mul = 12; ll add=e[a][b][c]*e[b][c][d]; add%=MOD; add*=e[a][c][d]; add%=MOD; add*=e[a][b][d]; add%=MOD; add*=mul; add%=MOD; ans+=add; ans%=MOD; } } } } } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...