Submission #898859

#	Time	Username	Problem	Language	Result	Execution time	Memory
898859		arashMLG	Cubeword (CEOI19_cubeword)	C++17	0 / 100	488 ms	4872 KiB

cubeword

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

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

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

const int N = 5e5 + 23;
const int K = 26 + 26;
const ll mod = 998244353;
const ll inf = 1e18;

//#define F         first
#define S         second
#define pb        push_back
#define sz(x)     ((int)x.size())
#define all(x)    x.begin(),x.end()
#define lc        (v<<1)
#define rc        ((v<<1)|1)
#define F(x)      for(int x = 0; x < K; x++)
#define debug(x)  cout<<#x << " : " << x << endl;
#define int       ll

int dp[K][K][K];
vector<string> s[11];
int cnt[K][K];
vector<pii> vec;
int val[300];
int javab = 0;

void solve(int len) {
	F(i) F(j) {
		cnt[i][j] = 0;
		F(k) dp[i][j][k] = 0;
	}
	sort(all(s[len]));
	s[len].resize(unique(all(s[len])) - s[len].begin());
	for(string t : s[len]) {
		cnt[val[t[0]]][val[t.back()]] ++;
		string tp = t;
		reverse(all(tp));
		if(tp != t) {
			cnt[val[t.back()]][val[t[0]]] ++;
		}
	}
	F(i) F(a) F(b) F(c) {
		(dp[a][b][c] += (1LL*cnt[min(i,a)][max(i,a)]*cnt[min(i,b)][max(i,b)]%mod*cnt[min(i,c)][max(i,c)] %mod)) %= mod;
	}
	int ans=0;
	F(a) F(b) F(c) F(d) {
		(ans += (dp[a][b][c] *dp[a][b][d]%mod*dp[a][c][d]%mod*dp[b][c][d])) %= mod;
	}
	(javab += ans) %=mod;
}

int32_t main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int x = 0;
	for(char c = 'a'; c<= 'z'; c++) {
		val[c] = x++;
	}
	for(char c = 'A'; c<= 'Z'; c++) {
		val[c] = x++;
	}
	for(char c = '0'; c <= '9'; c++) {
		val[c] = x ++;
	}
	int n; cin>>n;
	for(int i = 0 ;i < n ; i++){ 
		string t; cin>>t;
		if(t[0] > t.back()) reverse(all(t));
		s[sz(t)].pb(t);
	}
	for(int i = 3; i <= 10; i ++) solve(i);
	cout<<javab%mod;
	return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'void solve(ll)':
cubeword.cpp:42:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |   cnt[val[t[0]]][val[t.back()]] ++;
      |               ^
cubeword.cpp:42:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |   cnt[val[t[0]]][val[t.back()]] ++;
      |                      ~~~~~~^~
cubeword.cpp:46:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |    cnt[val[t.back()]][val[t[0]]] ++;
      |            ~~~~~~^~
cubeword.cpp:46:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   46 |    cnt[val[t.back()]][val[t[0]]] ++;
      |                               ^
cubeword.cpp: In function 'int32_t main()':
cubeword.cpp:63:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |   val[c] = x++;
      |       ^
cubeword.cpp:66:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |   val[c] = x++;
      |       ^
cubeword.cpp:69:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |   val[c] = x ++;
      |       ^

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