Submission #1085514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085514		serifefedartar	Trener (COCI20_trener)	C++17	110 / 110	670 ms	4728 KiB

trener

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;

#define int long long
ll expo(ll A, ll B, ll M) {
    ll res = 1;
    while (B) {
        if (B & 1)
            res = (res * A) % M;
        A = (A * A) % M;
        B /= 2;
    }
    return res;
}

const ll P = 37;
const ll MD = 1e9 + 9;

ll hashes[55][1505], dp[55][1505];
pair<ll,ll> pair_hash[55][1505];

signed main() {
    fast;
    int N, K;
    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            vector<ll> hh(i+1, 0);
            string s;
            cin >> s;
            s = "#" + s;
            for (int k = 1; k <= i; k++) 
                hh[k] = (hh[k-1] * P + (s[k] - 'a' + 1)) % MD;
            hashes[i][j] = hh[i];
            pair_hash[i][j] = {hh[i-1], (hh[i] - hh[1] * expo(P, i-1, MD) % MD + MD) % MD};
        }
    }

    for (int i = 1; i <= K; i++)
        dp[1][i] = 1;
    for (int i = 2; i <= N; i++) {
        for (int k = 1; k <= K; k++) {
            for (int old_k = 1; old_k <= K; old_k++) {
                if (hashes[i-1][old_k] == pair_hash[i][k].f || hashes[i-1][old_k] == pair_hash[i][k].s)
                    dp[i][k] = (dp[i][k] + dp[i-1][old_k]) % MOD;
            }
        }
    }

    ll ans = 0;
    for (int k = 1; k <= K; k++)
        ans = (ans + dp[N][k]) % MOD;
    cout << ans << "\n";
}

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