Submission #999010

#	Time	Username	Problem	Language	Result	Execution time	Memory
999010		vjudge1	Trener (COCI20_trener)	C++17	55 / 110	429 ms	13704 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, hsh[N][K], inv = 696011009, pwr[N];
vector<pair<ll, ll>> g[N][K];
map<ll, ll> cnt[N], dp[N];

int main(){
    pwr[0] = 1;
    for (ll i = 1; i < N; i ++)
        pwr[i] = (pwr[i - 1] * base) % mod;

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

            for (char c : s)
                hsh[i][j] = (hsh[i][j] * base + c) % mod;
            cnt[i][hsh[i][j]]++;
            dp[i][hsh[i][j]]++;
        }
    }

    // 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 [H, C] : cnt[i]){
            ll sm = 0;
            // cout << "HASH = " << H << endl;
            map<int, bool> seen;
            for (int c = 'a'; c <= 'z'; c ++){
                ll nh = (H * base + c) % mod;
                // cout << "can have edge with " << nh << endl;
                if (!seen[nh] and dp[i + 1].find(nh) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][nh]) % mod;
                seen[nh] = 1;

                nh = (H + pwr[i] * c) % mod;
                // cout << "can have edge with " << nh << endl;
                if (!seen[nh] and dp[i + 1].find(nh) != dp[i + 1].end())
                    sm = (sm + dp[i + 1][nh]) % mod;
                seen[nh] = 1;
            }

            dp[i][H] = 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 [H, val] : dp[1])
        ans = (ans + val) % mod;
    cout << ans << endl;
}

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