Submission #999015

#	Time	Username	Problem	Language	Result	Execution time	Memory
999015		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	747 ms	16700 KiB

trener

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 55, K = 1505;
const ll base = 727, mod = 1e9 + 7;

ll n, k;
map<string, ll> cnt[N], dp[N];

int main(){
    cin >> n >> k;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= k; j ++){
            string s;
            cin >> s;

            cnt[i][s]++;
            dp[i][s]++;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    for (ll i = n - 1; i > 0; i --){
        for (auto [S, C] : cnt[i]){
            ll sm = 0;
            // cout << "HASH = " << H << endl;
            string pref = S + '#';
            string suff = '#' + S;
            map<string, bool> seen;
            for (int c = 'a'; c <= 'z'; c ++){
                // cout << "can have edge with " << nh << endl;
                pref[i] = suff[0] = c;

                if (!seen[pref] and dp[i + 1].find(pref) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][pref]) % mod;
                seen[pref] = 1;

                if (!seen[suff] and dp[i + 1].find(suff) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][suff]) % mod;
                seen[suff] = 1;
            }

            dp[i][S] = C * sm % mod;
        }
    }

    // cout << endl;
    // for (int i = 1; i <= n; i ++){
    //     cout << i << " : ";
    //     for (auto [H, val] : dp[i])
    //         cout << H << " -- " << val << ", ";
    //     cout << endl;
    // }
    // cout << endl;

    ll ans = 0;
    for (auto [S, val] : dp[1])
        ans = (ans + val) % mod;
    cout << ans << endl;
}

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