oj.uz

Submission #845164

# Submission time Handle Problem Language Result Execution time Memory
845164 2023-09-06T12:22:36 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 988 ms 19388 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define all(c) (c).begin(), (c).end()

const int mod = 1e9 + 7,base = 37;
int dp[55][1505],val[55][1505],pw[1505],n,k;

int binpow(int x,int y){
	int res = 1;
	while(y > 0){
		if(y % 2) res = res * x % mod;
		x = x * x % mod;
		y /= 2;
	}
	return res;
}

void solve(){	

	pw[0] = 1;
	for(int i = 1; i < 1505; i++){
		pw[i] = (pw[i - 1] * base) % mod;
	}

	cin >> n >> k;
	vector<string> s[n];
	for(int i = 0; i < n; i++){
		s[i].resize(k);
		for(int j = 0; j < k; ++j){
			cin >> s[i][j];
		}
	}
		
	vector<set<int>> st[n];
	for(int j = 0; j < k; j++){
		dp[0][j] = 1;
	}

	for(int i = 0; i < n; i++){
		st[i].resize(k);
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			for(int t = 0; t < i + 1; t++){
				if(t == i) st[i][j].insert(val[i][j]);
				val[i][j] = (val[i][j] + (s[i][j][t] - 'a' + 1) * pw[t]) % mod;
			}
			int cur = 0;
			for(int t = 1; t < i + 1; t++){
				cur = (cur + (s[i][j][t] - 'a' + 1) * pw[t - 1]) % mod;
			} 
			st[i][j].insert(cur);
		}
	}


	for(int i = 0; i + 1 < n; i++){
		for(int j = 0; j < k; j++){
			for(int t = 0; t < k; t++){
				if(st[i + 1][t].count(val[i][j])){
					dp[i + 1][t] = (dp[i + 1][t] + dp[i][j]) % mod;
				}
			}
		}
	}


	int ans = 0;
	for(int i = 0; i < k; i++){
		ans = (ans + dp[n - 1][i]) % mod;
	}

	cout << ans << endl;
}

signed main(){

	#ifndef ONLINE_JUDGE
	//	freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
	#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--){
		solve();
	}

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1880 KB Output is correct
2 Correct 6 ms 1884 KB Output is correct
3 Correct 6 ms 1884 KB Output is correct
4 Correct 4 ms 1880 KB Output is correct
5 Correct 6 ms 2028 KB Output is correct
6 Correct 6 ms 1884 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1880 KB Output is correct
6 Correct 6 ms 1884 KB Output is correct
7 Correct 6 ms 1884 KB Output is correct
8 Correct 4 ms 1880 KB Output is correct
9 Correct 6 ms 2028 KB Output is correct
10 Correct 6 ms 1884 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 988 ms 19388 KB Output is correct
13 Correct 941 ms 19192 KB Output is correct
14 Correct 962 ms 19112 KB Output is correct
15 Correct 947 ms 19016 KB Output is correct
16 Correct 255 ms 15592 KB Output is correct
17 Correct 918 ms 19056 KB Output is correct
18 Correct 894 ms 19084 KB Output is correct
19 Correct 908 ms 19284 KB Output is correct
20 Correct 895 ms 19092 KB Output is correct
21 Correct 914 ms 18988 KB Output is correct
22 Correct 273 ms 15480 KB Output is correct