oj.uz

Submission #276154

# Submission time Handle Problem Language Result Execution time Memory
276154 2020-08-20T11:11:04 Z theStaticMind Cubeword (CEOI19_cubeword) C++14
50 / 100
 446 ms 16376 KB 
#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 = 16;

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

map<char, int> ptr;

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

	clear();

	/*for(auto p : cnt){
		cout << p.first.first << "-" << p.first.second << "=>" << p.second << "\n";
	}*/

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

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

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					dp[a][b][c][d] = 0;
				}
			}
		}
	}

	for(int a = 0; a < k; a++){
		for(int f = 0; f < k; f++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					for(int h = 0; h < k; h++){
						dp[a][f][c][h] += dp2[a][f][c][d] * cnt[d][h] % mod * cnt[f][h] % mod;
						dp[a][f][c][h] %= mod;
					}
				}
			}
		}
	}

	for(int a = 0; a < k; a++){
		for(int b = 0; b < k; b++){
			for(int c = 0; c < k; c++){
				for(int d = 0; d < k; d++){
					dp2[a][b][c][d] = 0;
				}
			}
		}
	}

	for(int a = 0; a < k; a++){
		for(int f = 0; f < k; f++){
			for(int c = 0; c < k; c++){
				for(int h = 0; h < k; h++){
					for(int g = 0; g < k; g++){
						dp2[a][f][g][h] += dp[a][f][c][h] * cnt[c][g] % mod * cnt[g][h] % mod;
						dp2[a][f][g][h] %= mod;
					}
				}
			}
		}
	}

	int ret = 0;

	for(int a = 0; a < k; a++){
		for(int f = 0; f < k; f++){
			for(int g = 0; g < k; g++){
				for(int h = 0; h < k; h++){
					for(int e = 0; e < k; e++){
						ret += dp2[a][f][g][h] * cnt[a][e] % mod * cnt[f][e] % mod * cnt[g][e] % mod;
						ret %= mod;
					}
				}
			}
		}
	}

	return ret;
}

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

	int n, 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 <= 'p'; i++) ptr[i] = 0;
//	for(char i = 'A'; i <= 'P'; 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

# Verdict Execution time Memory Grader output
1 Correct 362 ms 15272 KB Output is correct
2 Correct 353 ms 16108 KB Output is correct
3 Correct 370 ms 16168 KB Output is correct
4 Correct 346 ms 16292 KB Output is correct
5 Correct 355 ms 16168 KB Output is correct
6 Correct 365 ms 16220 KB Output is correct
7 Correct 371 ms 16292 KB Output is correct
8 Correct 379 ms 16216 KB Output is correct
9 Correct 365 ms 16152 KB Output is correct
10 Correct 388 ms 16168 KB Output is correct
11 Correct 395 ms 16160 KB Output is correct
12 Correct 392 ms 16108 KB Output is correct
13 Correct 348 ms 16168 KB Output is correct
14 Correct 351 ms 16168 KB Output is correct
15 Correct 446 ms 16168 KB Output is correct
16 Correct 344 ms 16168 KB Output is correct
17 Correct 404 ms 16172 KB Output is correct
18 Correct 371 ms 16184 KB Output is correct
19 Correct 388 ms 16168 KB Output is correct
20 Correct 343 ms 16296 KB Output is correct
21 Correct 405 ms 16296 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 15272 KB Output is correct
2 Correct 353 ms 16108 KB Output is correct
3 Correct 370 ms 16168 KB Output is correct
4 Correct 346 ms 16292 KB Output is correct
5 Correct 355 ms 16168 KB Output is correct
6 Correct 365 ms 16220 KB Output is correct
7 Correct 371 ms 16292 KB Output is correct
8 Correct 379 ms 16216 KB Output is correct
9 Correct 365 ms 16152 KB Output is correct
10 Correct 388 ms 16168 KB Output is correct
11 Correct 395 ms 16160 KB Output is correct
12 Correct 392 ms 16108 KB Output is correct
13 Correct 348 ms 16168 KB Output is correct
14 Correct 351 ms 16168 KB Output is correct
15 Correct 446 ms 16168 KB Output is correct
16 Correct 344 ms 16168 KB Output is correct
17 Correct 404 ms 16172 KB Output is correct
18 Correct 371 ms 16184 KB Output is correct
19 Correct 388 ms 16168 KB Output is correct
20 Correct 343 ms 16296 KB Output is correct
21 Correct 405 ms 16296 KB Output is correct
22 Correct 379 ms 15992 KB Output is correct
23 Correct 351 ms 16088 KB Output is correct
24 Correct 356 ms 15992 KB Output is correct
25 Correct 390 ms 16120 KB Output is correct
26 Correct 358 ms 16080 KB Output is correct
27 Correct 376 ms 16048 KB Output is correct
28 Correct 365 ms 16160 KB Output is correct
29 Correct 356 ms 16120 KB Output is correct
30 Correct 378 ms 15992 KB Output is correct
31 Correct 355 ms 15992 KB Output is correct
32 Correct 344 ms 15992 KB Output is correct
33 Correct 343 ms 15992 KB Output is correct
34 Correct 343 ms 15992 KB Output is correct
35 Correct 329 ms 16120 KB Output is correct
36 Correct 339 ms 15992 KB Output is correct
37 Correct 345 ms 16152 KB Output is correct
38 Correct 365 ms 16172 KB Output is correct
39 Correct 356 ms 16120 KB Output is correct
40 Correct 338 ms 15992 KB Output is correct
41 Correct 372 ms 16120 KB Output is correct
42 Correct 387 ms 16120 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 15272 KB Output is correct
2 Correct 353 ms 16108 KB Output is correct
3 Correct 370 ms 16168 KB Output is correct
4 Correct 346 ms 16292 KB Output is correct
5 Correct 355 ms 16168 KB Output is correct
6 Correct 365 ms 16220 KB Output is correct
7 Correct 371 ms 16292 KB Output is correct
8 Correct 379 ms 16216 KB Output is correct
9 Correct 365 ms 16152 KB Output is correct
10 Correct 388 ms 16168 KB Output is correct
11 Correct 395 ms 16160 KB Output is correct
12 Correct 392 ms 16108 KB Output is correct
13 Correct 348 ms 16168 KB Output is correct
14 Correct 351 ms 16168 KB Output is correct
15 Correct 446 ms 16168 KB Output is correct
16 Correct 344 ms 16168 KB Output is correct
17 Correct 404 ms 16172 KB Output is correct
18 Correct 371 ms 16184 KB Output is correct
19 Correct 388 ms 16168 KB Output is correct
20 Correct 343 ms 16296 KB Output is correct
21 Correct 405 ms 16296 KB Output is correct
22 Correct 379 ms 15992 KB Output is correct
23 Correct 351 ms 16088 KB Output is correct
24 Correct 356 ms 15992 KB Output is correct
25 Correct 390 ms 16120 KB Output is correct
26 Correct 358 ms 16080 KB Output is correct
27 Correct 376 ms 16048 KB Output is correct
28 Correct 365 ms 16160 KB Output is correct
29 Correct 356 ms 16120 KB Output is correct
30 Correct 378 ms 15992 KB Output is correct
31 Correct 355 ms 15992 KB Output is correct
32 Correct 344 ms 15992 KB Output is correct
33 Correct 343 ms 15992 KB Output is correct
34 Correct 343 ms 15992 KB Output is correct
35 Correct 329 ms 16120 KB Output is correct
36 Correct 339 ms 15992 KB Output is correct
37 Correct 345 ms 16152 KB Output is correct
38 Correct 365 ms 16172 KB Output is correct
39 Correct 356 ms 16120 KB Output is correct
40 Correct 338 ms 15992 KB Output is correct
41 Correct 372 ms 16120 KB Output is correct
42 Correct 387 ms 16120 KB Output is correct
43 Incorrect 359 ms 16376 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 15272 KB Output is correct
2 Correct 353 ms 16108 KB Output is correct
3 Correct 370 ms 16168 KB Output is correct
4 Correct 346 ms 16292 KB Output is correct
5 Correct 355 ms 16168 KB Output is correct
6 Correct 365 ms 16220 KB Output is correct
7 Correct 371 ms 16292 KB Output is correct
8 Correct 379 ms 16216 KB Output is correct
9 Correct 365 ms 16152 KB Output is correct
10 Correct 388 ms 16168 KB Output is correct
11 Correct 395 ms 16160 KB Output is correct
12 Correct 392 ms 16108 KB Output is correct
13 Correct 348 ms 16168 KB Output is correct
14 Correct 351 ms 16168 KB Output is correct
15 Correct 446 ms 16168 KB Output is correct
16 Correct 344 ms 16168 KB Output is correct
17 Correct 404 ms 16172 KB Output is correct
18 Correct 371 ms 16184 KB Output is correct
19 Correct 388 ms 16168 KB Output is correct
20 Correct 343 ms 16296 KB Output is correct
21 Correct 405 ms 16296 KB Output is correct
22 Correct 379 ms 15992 KB Output is correct
23 Correct 351 ms 16088 KB Output is correct
24 Correct 356 ms 15992 KB Output is correct
25 Correct 390 ms 16120 KB Output is correct
26 Correct 358 ms 16080 KB Output is correct
27 Correct 376 ms 16048 KB Output is correct
28 Correct 365 ms 16160 KB Output is correct
29 Correct 356 ms 16120 KB Output is correct
30 Correct 378 ms 15992 KB Output is correct
31 Correct 355 ms 15992 KB Output is correct
32 Correct 344 ms 15992 KB Output is correct
33 Correct 343 ms 15992 KB Output is correct
34 Correct 343 ms 15992 KB Output is correct
35 Correct 329 ms 16120 KB Output is correct
36 Correct 339 ms 15992 KB Output is correct
37 Correct 345 ms 16152 KB Output is correct
38 Correct 365 ms 16172 KB Output is correct
39 Correct 356 ms 16120 KB Output is correct
40 Correct 338 ms 15992 KB Output is correct
41 Correct 372 ms 16120 KB Output is correct
42 Correct 387 ms 16120 KB Output is correct
43 Incorrect 359 ms 16376 KB Output isn't correct
44 Halted 0 ms 0 KB -