# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
524522 | 2022-02-09T11:55:10 Z | tato | Trener (COCI20_trener) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; long long p = 1e9+7; map <string, long long > mp; long long pas = 0; int n,k; vector <string > v[51]; long long g[51][1501]; int used[51][1501]; bool check(string s, string l) { string t = l.substr(0,l.size() - 1); string f = l.substr(1); if(s == t or s == f) return true; else return false; } long long dfs(pair <int,int> par,int m) { if(m == n + 1) return 1; if(used[par.first][par.second] == 1) return g[par.first][par.second]; used[par.firs t][par.second] = 1; for(int i = 0; i < k; i++) if(check(v[par.first][par.second], v[m][i])) { long long cnt = dfs({m,i}, m + 1); g[par.first][par.second] = (g[par.first][par.second] + cnt) % p; } return g[par.first][par.second]; } void answer() { string s; cin >> n >> k; for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) { cin >> s; v[i].push_back(s); } for (int i = 0; i < k; i++) pas = (dfs({1,i},2) + pas) % p; cout << pas; } int main() { int t = 1; //cin >> t; while(t--) answer(); return 0; }