Submission #223218

#	Time	Username	Problem	Language	Result	Execution time	Memory
223218		oolimry	Trener (COCI20_trener)	C++14	110 / 110	1987 ms	28088 KiB

trener

#include <bits/stdc++.h>

using namespace std;
long long mod = 1000000007;

unordered_map<string, long long> m;
unordered_map<string, long long> mm;

inline void prop(string s, long long x){
	//cout << s << " " << x << "\n";
	if(x == 0) return;
	for(char c = 'a';c <= 'z';c++){
		//cout << s+c << " " << c+s << "\n";
		string a = s + c;
		string b = c + s;
		long long res = mm[a];
		res += x;
		if(res >= mod) res -= mod;
		mm[a] = res;
		
		if(a != b){
			res = mm[b];
			res += x;
			if(res >= mod) res -= mod;
			mm[b] = res;
		}
	}
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k; cin >> n >> k;
	
	if(n == 1){
		cout << k;
		return 0;
	}
	
	for(int j = 0;j < k;j++){
		string s; cin >> s;
		prop(s, 1);
	}
	
	for(int i = 2;i <= n-1;i++){
		swap(m, mm);
		mm.clear();
		for(int j = 0;j < k;j++){
			string s; cin >> s;
			prop(s, m[s]);
		}
	}
	
	long long ans = 0;
	for(int j = 0;j < k;j++){
		string s; cin >> s;
		ans += mm[s];
		//cout << mm[s] << "\n";
	}
	
	ans %= mod;
	cout << ans;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55