Submission #946771

#	Time	Username	Problem	Language	Result	Execution time	Memory
946771		berr	Cubeword (CEOI19_cubeword)	C++17	100 / 100	575 ms	25864 KiB

cubeword

#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;
#define int long long

map<char, int> mp;
int c[11][62][62][62];
int aa[11][63][63];

const int mod = 998244353;

int mul(int x, int y){
	if((x*y)>mod) return x*y%mod;
	return x*y;
}

void sum(int &a){
	if(a>=mod) a-=mod;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int cnt=0;

	for(int i='a'; i<='z'; i++) mp[i]=cnt++;
	for(int i='A'; i<='Z'; i++)	mp[i]=cnt++;
	for(int i='0'; i<='9'; i++)	mp[i]=cnt++;
	
	int n; cin>>n;
	vector<string> s(n), x;
		
	for(auto &i: s){
		cin >> i;
		string x = i;
		reverse(x.begin(), x.end());
		if(x<i) i=x;
	}

	sort(s.begin(), s.end());
	for(int i=0; i<n; i++){
		if(i==0||s[i]!=s[i-1]) x.push_back(s[i]);
	}

	s=x;
	n = s.size();	

	for(int i=0; i<n; i++){
		string x=s[i];
		reverse(x.begin(), x.end());
		if(x==s[i]) aa[x.size()][mp[x[0]]][mp[x.back()]]++;
		else aa[x.size()][mp[x[0]]][mp[x.back()]]++, aa[x.size()][mp[x.back()]][mp[x[0]]]++;
	}
	for(int i=3; i<=10; i++){
		for(int j=0; j<62; j++){
			for(int a=0; a<62; a++){
				for(int b=0; b<62; b++){
					for(int cc=0; cc<62; cc++){
						c[i][a][b][cc] += mul(aa[i][j][a], mul(aa[i][j][b], aa[i][j][cc]));
						sum(c[i][a][b][cc]);
					}
				}
			}
		}
	}

	int ans=0;
	for(int i=3; i<=10; i++){
		for(int j=0; j<62; j++){
			for(int a=0; a<62; a++){
				for(int b=0; b<62; b++){
					for(int cc=0; cc<62; cc++){
						ans += mul(mul(c[i][j][a][b], c[i][j][a][cc]), mul(c[i][a][b][cc], c[i][j][b][cc]));
						sum(ans);
					}
				}
			}
		}

	}

	cout<<ans;

}   

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