답안 #276903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
276903	2020-08-20T18:30:15 Z	theStaticMind	Cubeword (CEOI19_cubeword)	C++14	100 / 100	307 ms	16632 KB

cubeword

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

const int k = 62;

int dp[k][k][k];
int cnt[k][k];

map<char, int> ptr;

int comb[2][2][2] = {{{24, 12}, {12, 4}}, {{12, 6}, {4, 1}}};

void clear(){
	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				dp[a][b][c] = 0;
			}
		}
	}
}
 
int solve(vector<vector<int>>& cnt){

	clear();

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int f = a; f < k; f++){
				for(int d = f; d < k; d++){
					dp[a][f][d] = (1ll * dp[a][f][d] + 1ll * cnt[b][a] * cnt[b][f] * cnt[b][d]) % mod;
				}
			}
		}
	} 

	int64_t ret = 0;
	for(int a = 0; a < k; a++){
		for(int f = a; f < k; f++){
			for(int g = f; g < k; g++){
				for(int d = g; d < k; d++){
					ret += 1ll * dp[a][f][d] * dp[f][g][d] % mod * dp[a][f][g] % mod * dp[a][g][d] % mod * comb[a==f][f==g][g==d];
					ret %= mod;
				}
			}
		}
	}
	


	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	int64_t ans = 0;
	cin >> n;

	unordered_set<string> S[11];
	vector<string> arr;

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		S[sz(s)].insert(s);
		reverse(all(s));
		S[sz(s)].insert(s);
	}

	for(char i = 'a'; i <= 'z'; i++) ptr[i] = 0;
	for(char i = 'A'; i <= 'Z'; i++) ptr[i] = 0;
	for(char i = '0'; i <= '9'; i++) ptr[i] = 0;

	int ind = 0;
	for(auto& p : ptr){
		p.second = ind++;
	}

	for(int i = 3; i <= 10; i++){ 
		if(S[i].empty()) continue;
		vector<vector<int> > cnt(k, vector<int>(k, 0));
		for(auto p : S[i]){
			cnt[ptr[p[0]]][ptr[p[i - 1]]]++;
		}

		ans += solve(cnt);
	}

	cout << ans % mod;
}

Subtask #1
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	267 ms	16040 KB	Output is correct
2	Correct	259 ms	16168 KB	Output is correct
3	Correct	275 ms	16084 KB	Output is correct
4	Correct	261 ms	16040 KB	Output is correct
5	Correct	283 ms	16040 KB	Output is correct
6	Correct	267 ms	16008 KB	Output is correct
7	Correct	289 ms	16088 KB	Output is correct
8	Correct	294 ms	16100 KB	Output is correct
9	Correct	267 ms	16040 KB	Output is correct
10	Correct	276 ms	16040 KB	Output is correct
11	Correct	275 ms	16044 KB	Output is correct
12	Correct	253 ms	16164 KB	Output is correct
13	Correct	257 ms	16168 KB	Output is correct
14	Correct	267 ms	16040 KB	Output is correct
15	Correct	289 ms	16040 KB	Output is correct
16	Correct	267 ms	16128 KB	Output is correct
17	Correct	299 ms	16216 KB	Output is correct
18	Correct	276 ms	16040 KB	Output is correct
19	Correct	277 ms	16040 KB	Output is correct
20	Correct	284 ms	16168 KB	Output is correct
21	Correct	297 ms	16168 KB	Output is correct

Subtask #2
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	267 ms	16040 KB	Output is correct
2	Correct	259 ms	16168 KB	Output is correct
3	Correct	275 ms	16084 KB	Output is correct
4	Correct	261 ms	16040 KB	Output is correct
5	Correct	283 ms	16040 KB	Output is correct
6	Correct	267 ms	16008 KB	Output is correct
7	Correct	289 ms	16088 KB	Output is correct
8	Correct	294 ms	16100 KB	Output is correct
9	Correct	267 ms	16040 KB	Output is correct
10	Correct	276 ms	16040 KB	Output is correct
11	Correct	275 ms	16044 KB	Output is correct
12	Correct	253 ms	16164 KB	Output is correct
13	Correct	257 ms	16168 KB	Output is correct
14	Correct	267 ms	16040 KB	Output is correct
15	Correct	289 ms	16040 KB	Output is correct
16	Correct	267 ms	16128 KB	Output is correct
17	Correct	299 ms	16216 KB	Output is correct
18	Correct	276 ms	16040 KB	Output is correct
19	Correct	277 ms	16040 KB	Output is correct
20	Correct	284 ms	16168 KB	Output is correct
21	Correct	297 ms	16168 KB	Output is correct
22	Correct	253 ms	15984 KB	Output is correct
23	Correct	277 ms	16084 KB	Output is correct
24	Correct	243 ms	15992 KB	Output is correct
25	Correct	287 ms	15968 KB	Output is correct
26	Correct	242 ms	15992 KB	Output is correct
27	Correct	247 ms	15996 KB	Output is correct
28	Correct	244 ms	16120 KB	Output is correct
29	Correct	238 ms	15992 KB	Output is correct
30	Correct	248 ms	16120 KB	Output is correct
31	Correct	248 ms	16120 KB	Output is correct
32	Correct	247 ms	15864 KB	Output is correct
33	Correct	252 ms	16052 KB	Output is correct
34	Correct	248 ms	15992 KB	Output is correct
35	Correct	241 ms	15992 KB	Output is correct
36	Correct	241 ms	15996 KB	Output is correct
37	Correct	235 ms	15992 KB	Output is correct
38	Correct	249 ms	16152 KB	Output is correct
39	Correct	238 ms	16120 KB	Output is correct
40	Correct	269 ms	16020 KB	Output is correct
41	Correct	268 ms	15992 KB	Output is correct
42	Correct	257 ms	15992 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	267 ms	16040 KB	Output is correct
2	Correct	259 ms	16168 KB	Output is correct
3	Correct	275 ms	16084 KB	Output is correct
4	Correct	261 ms	16040 KB	Output is correct
5	Correct	283 ms	16040 KB	Output is correct
6	Correct	267 ms	16008 KB	Output is correct
7	Correct	289 ms	16088 KB	Output is correct
8	Correct	294 ms	16100 KB	Output is correct
9	Correct	267 ms	16040 KB	Output is correct
10	Correct	276 ms	16040 KB	Output is correct
11	Correct	275 ms	16044 KB	Output is correct
12	Correct	253 ms	16164 KB	Output is correct
13	Correct	257 ms	16168 KB	Output is correct
14	Correct	267 ms	16040 KB	Output is correct
15	Correct	289 ms	16040 KB	Output is correct
16	Correct	267 ms	16128 KB	Output is correct
17	Correct	299 ms	16216 KB	Output is correct
18	Correct	276 ms	16040 KB	Output is correct
19	Correct	277 ms	16040 KB	Output is correct
20	Correct	284 ms	16168 KB	Output is correct
21	Correct	297 ms	16168 KB	Output is correct
22	Correct	253 ms	15984 KB	Output is correct
23	Correct	277 ms	16084 KB	Output is correct
24	Correct	243 ms	15992 KB	Output is correct
25	Correct	287 ms	15968 KB	Output is correct
26	Correct	242 ms	15992 KB	Output is correct
27	Correct	247 ms	15996 KB	Output is correct
28	Correct	244 ms	16120 KB	Output is correct
29	Correct	238 ms	15992 KB	Output is correct
30	Correct	248 ms	16120 KB	Output is correct
31	Correct	248 ms	16120 KB	Output is correct
32	Correct	247 ms	15864 KB	Output is correct
33	Correct	252 ms	16052 KB	Output is correct
34	Correct	248 ms	15992 KB	Output is correct
35	Correct	241 ms	15992 KB	Output is correct
36	Correct	241 ms	15996 KB	Output is correct
37	Correct	235 ms	15992 KB	Output is correct
38	Correct	249 ms	16152 KB	Output is correct
39	Correct	238 ms	16120 KB	Output is correct
40	Correct	269 ms	16020 KB	Output is correct
41	Correct	268 ms	15992 KB	Output is correct
42	Correct	257 ms	15992 KB	Output is correct
43	Correct	280 ms	16376 KB	Output is correct
44	Correct	273 ms	16376 KB	Output is correct
45	Correct	292 ms	16324 KB	Output is correct
46	Correct	304 ms	16248 KB	Output is correct
47	Correct	257 ms	16248 KB	Output is correct
48	Correct	255 ms	16248 KB	Output is correct
49	Correct	261 ms	16248 KB	Output is correct
50	Correct	259 ms	16248 KB	Output is correct
51	Correct	267 ms	16248 KB	Output is correct
52	Correct	274 ms	16376 KB	Output is correct
53	Correct	307 ms	16376 KB	Output is correct
54	Correct	300 ms	16236 KB	Output is correct
55	Correct	268 ms	16248 KB	Output is correct
56	Correct	273 ms	16248 KB	Output is correct
57	Correct	265 ms	16252 KB	Output is correct
58	Correct	264 ms	16248 KB	Output is correct
59	Correct	278 ms	16376 KB	Output is correct
60	Correct	258 ms	16248 KB	Output is correct
61	Correct	271 ms	16288 KB	Output is correct
62	Correct	268 ms	16248 KB	Output is correct
63	Correct	270 ms	16248 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	267 ms	16040 KB	Output is correct
2	Correct	259 ms	16168 KB	Output is correct
3	Correct	275 ms	16084 KB	Output is correct
4	Correct	261 ms	16040 KB	Output is correct
5	Correct	283 ms	16040 KB	Output is correct
6	Correct	267 ms	16008 KB	Output is correct
7	Correct	289 ms	16088 KB	Output is correct
8	Correct	294 ms	16100 KB	Output is correct
9	Correct	267 ms	16040 KB	Output is correct
10	Correct	276 ms	16040 KB	Output is correct
11	Correct	275 ms	16044 KB	Output is correct
12	Correct	253 ms	16164 KB	Output is correct
13	Correct	257 ms	16168 KB	Output is correct
14	Correct	267 ms	16040 KB	Output is correct
15	Correct	289 ms	16040 KB	Output is correct
16	Correct	267 ms	16128 KB	Output is correct
17	Correct	299 ms	16216 KB	Output is correct
18	Correct	276 ms	16040 KB	Output is correct
19	Correct	277 ms	16040 KB	Output is correct
20	Correct	284 ms	16168 KB	Output is correct
21	Correct	297 ms	16168 KB	Output is correct
22	Correct	253 ms	15984 KB	Output is correct
23	Correct	277 ms	16084 KB	Output is correct
24	Correct	243 ms	15992 KB	Output is correct
25	Correct	287 ms	15968 KB	Output is correct
26	Correct	242 ms	15992 KB	Output is correct
27	Correct	247 ms	15996 KB	Output is correct
28	Correct	244 ms	16120 KB	Output is correct
29	Correct	238 ms	15992 KB	Output is correct
30	Correct	248 ms	16120 KB	Output is correct
31	Correct	248 ms	16120 KB	Output is correct
32	Correct	247 ms	15864 KB	Output is correct
33	Correct	252 ms	16052 KB	Output is correct
34	Correct	248 ms	15992 KB	Output is correct
35	Correct	241 ms	15992 KB	Output is correct
36	Correct	241 ms	15996 KB	Output is correct
37	Correct	235 ms	15992 KB	Output is correct
38	Correct	249 ms	16152 KB	Output is correct
39	Correct	238 ms	16120 KB	Output is correct
40	Correct	269 ms	16020 KB	Output is correct
41	Correct	268 ms	15992 KB	Output is correct
42	Correct	257 ms	15992 KB	Output is correct
43	Correct	280 ms	16376 KB	Output is correct
44	Correct	273 ms	16376 KB	Output is correct
45	Correct	292 ms	16324 KB	Output is correct
46	Correct	304 ms	16248 KB	Output is correct
47	Correct	257 ms	16248 KB	Output is correct
48	Correct	255 ms	16248 KB	Output is correct
49	Correct	261 ms	16248 KB	Output is correct
50	Correct	259 ms	16248 KB	Output is correct
51	Correct	267 ms	16248 KB	Output is correct
52	Correct	274 ms	16376 KB	Output is correct
53	Correct	307 ms	16376 KB	Output is correct
54	Correct	300 ms	16236 KB	Output is correct
55	Correct	268 ms	16248 KB	Output is correct
56	Correct	273 ms	16248 KB	Output is correct
57	Correct	265 ms	16252 KB	Output is correct
58	Correct	264 ms	16248 KB	Output is correct
59	Correct	278 ms	16376 KB	Output is correct
60	Correct	258 ms	16248 KB	Output is correct
61	Correct	271 ms	16288 KB	Output is correct
62	Correct	268 ms	16248 KB	Output is correct
63	Correct	270 ms	16248 KB	Output is correct
64	Correct	287 ms	16504 KB	Output is correct
65	Correct	280 ms	16632 KB	Output is correct
66	Correct	278 ms	16632 KB	Output is correct
67	Correct	294 ms	16504 KB	Output is correct
68	Correct	267 ms	16504 KB	Output is correct
69	Correct	266 ms	16504 KB	Output is correct
70	Correct	279 ms	16632 KB	Output is correct
71	Correct	254 ms	16504 KB	Output is correct
72	Correct	288 ms	16512 KB	Output is correct
73	Correct	259 ms	16632 KB	Output is correct
74	Correct	252 ms	16504 KB	Output is correct
75	Correct	258 ms	16376 KB	Output is correct
76	Correct	253 ms	16504 KB	Output is correct
77	Correct	288 ms	16444 KB	Output is correct
78	Correct	288 ms	16536 KB	Output is correct
79	Correct	268 ms	16548 KB	Output is correct
80	Correct	293 ms	16600 KB	Output is correct
81	Correct	248 ms	16504 KB	Output is correct
82	Correct	261 ms	16504 KB	Output is correct
83	Correct	255 ms	16504 KB	Output is correct
84	Correct	247 ms	16504 KB	Output is correct

답안 #276903

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 29.0 / 29.0

Subtask #3 34.0 / 34.0

Subtask #4 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
29.0 / 29.0

Subtask #3
34.0 / 34.0

Subtask #4
16.0 / 16.0