oj.uz

답안 #578883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
578883 2022-06-18T07:19:49 Z amunduzbaev Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 7424 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;

const int N = 1e5 + 5;
const int M = 62;
const int mod = 119 << 23 | 1;
int is[M][M], pre[M][M][M];

int bp(int a, int b){
	int c=1;
	while(b){
		if(b&1) c = c * 1ll * a % mod;
		a = a * 1ll * a % mod, b >>= 1;
	} return c;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<string> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		for(auto& x : a[i]){
			if('a' <= x && x <= 'z') x = x - 'a';
			if('A' <= x && x <= 'Z') x = x - 'A' + 26;
			if('0' <= x && x <= '9') x = x - '0' + 52;
		}
	}
	//~ sort(a.begin(), a.end());
	//~ a.erase(unique(a.begin(), a.end()), a.end());
	//~ vector<string> b;
	//~ for(int i=0;i<n;i++){
		//~ if(!i || a[i] != a[i-1]) b.push_back(a[i]);
	//~ }
	
	//~ swap(a, b);
	
	sort(a.begin(), a.end(), [&](string& a, string& b){
		return a.size() < b.size();
	});
	
	int l = 0, tot = 0;
	for(int s=3;s<=10;s++){
		memset(is, 0, sizeof is);
		int k = l;
		set<string> ss;
		while(l < n && (int)a[l].size() == s){
			string b = a[l];
			reverse(b.begin(), b.end());
			ss.insert(a[l]);
			ss.insert(b);
			l++;
		}
		if(l == k) continue;
		for(auto x : ss){
			is[x[0]][x[s - 1]]++;
		}
		memset(pre, 0, sizeof pre);
		
		for(int i=0;i<M;i++){
			for(int j=0;j<M;j++){
				for(int k=0;k<M;k++){
					for(int l=0;l<M;l++){
						pre[i][j][k] = (pre[i][j][k] + is[i][l] * 1ll * is[j][l] % mod * is[k][l]) % mod;
					}
					//~ if(pre[i][j][k]){
						//~ cout<<i<<" "<<j<<" "<<k<<"\n";
						//~ cout<<pre[i][j][k]<<"\n";
					//~ }
				}
			}
		}
		
		for(int i=0;i<M;i++){
			for(int j=0;j<M;j++){
				for(int k=0;k<M;k++){
					for(int l=0;l<M;l++){
						int res = 1;
						res = res * 1ll * pre[i][j][k] % mod;
						res = res * 1ll * pre[i][j][l] % mod;
						res = res * 1ll * pre[i][k][l] % mod;
						res = res * 1ll * pre[j][k][l] % mod;
						tot = (tot + res) % mod;
					}
				}
			}
		}
	}
	
	//~ cout<<tot<<"\n";
	//~ tot = tot * 1ll * bp(6, mod - 2) % mod;
	cout<<tot<<"\n";
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:60:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |    is[x[0]][x[s - 1]]++;
      |           ^
cubeword.cpp:60:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |    is[x[0]][x[s - 1]]++;
      |                     ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1185 ms 7424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1185 ms 7424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1185 ms 7424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1185 ms 7424 KB Time limit exceeded
2 Halted 0 ms 0 KB -