Submission #203786

#	Time	Username	Problem	Language	Result	Execution time	Memory
203786		dndhk	Cubeword (CEOI19_cubeword)	C++14	84 / 100	1190 ms	8784 KiB

cubeword

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const ll MOD = 998244353;
const int MAX_N = 100000;
const int MAX_K = 62;

int N;
vector<string> str[11];
set<string> st;
ll cnt[MAX_K+1][MAX_K+1];
ll cnt2[MAX_K+1][MAX_K+1][MAX_K+1];
string s;

ll ans = 0;

int calc(char c){
	if(c>='0' && c<='9'){
		return c-'0';
	}
	if(c>='A' && c<='Z'){
		return c-'A'+10;
	}
	if(c>='a' && c<='z'){
		return c-'a'+36;
	}
}

void solve(){
	for(int i=0; i<MAX_K; i++){ 
		for(int j=0; j<MAX_K; j++){
			for(int k=0; k<MAX_K; k++){
				cnt2[i][j][k] = 0;
				for(int t=0; t<MAX_K; t++){
					cnt2[i][j][k] = (cnt2[i][j][k] + (cnt[i][t] * cnt[j][t] * cnt[k][t] % MOD)) %  MOD;
				}
			}
		}
	}
	for(int i=0; i<MAX_K; i++){
		for(int j=0; j<MAX_K; j++){
			for(int k=0; k<MAX_K; k++){
				if(cnt2[i][j][k]==0)	continue;
				for(int t=0; t<MAX_K; t++){
					ll d = cnt2[i][j][k]; d = (d * cnt2[i][j][t]) % MOD; d = (d * cnt2[i][k][t]) % MOD; d = (d * cnt2[j][k][t]) % MOD;
					//if(d!=0)	cout<<i<<" "<<j<<" "<<k<<" "<<t<<" "<<d<<endl;
					ans = (ans + d) % MOD;
				}
			}
		}
	}
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		cin>>s;
		str[s.size()].pb(s);
	}
	for(int l=3; l<=10; l++){
		if(str[l].empty())	continue;
		st.clear();
		for(int j=0; j<MAX_K; j++){
			for(int k=0; k<MAX_K; k++){
				cnt[j][k] = 0;
			}
		}
		while(!str[l].empty()){
			s = str[l].back(); str[l].pop_back();
			if(st.find(s)==st.end()){
				st.insert(s);
				cnt[calc(s[0])][calc(s.back())]++;
			}
			for(int i=0; i<l/2; i++){
				char c = s[i]; s[i] = s[l-1-i]; s[l-1-i] = c;
			}
			if(st.find(s)==st.end()){
				st.insert(s);
				cnt[calc(s[0])][calc(s.back())]++;
			}
		}
 		solve();
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'int calc(char)':
cubeword.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
cubeword.cpp: In function 'int main()':
cubeword.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~

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