Submission #845164

#	Time	Username	Problem	Language	Result	Execution time	Memory
845164		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	988 ms	19388 KiB

trener

#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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55