Submission #223209

#	Time	Username	Problem	Language	Result	Execution time	Memory
223209		oolimry	Trener (COCI20_trener)	C++14	55 / 110	2019 ms	26568 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;

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";
		mm[s+c] += x;
		if(s + c != c + s) mm[c+s] += x;
		while(mm[c+s] >= mod) mm[c+s] -= mod;
	}
}

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];
	}
	
	ans %= mod;
	cout << ans;
}

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