oj.uz

Submission #1085514

# Submission time Handle Problem Language Result Execution time Memory
1085514 2024-09-08T11:10:26 Z serifefedartar Trener (COCI20_trener) C++17
110 / 110
 670 ms 4728 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 2 ms 1232 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 5 ms 1116 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 5 ms 1116 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 5 ms 1116 KB Output is correct
12 Correct 102 ms 4692 KB Output is correct
13 Correct 95 ms 4668 KB Output is correct
14 Correct 117 ms 4712 KB Output is correct
15 Correct 102 ms 4728 KB Output is correct
16 Correct 670 ms 4704 KB Output is correct
17 Correct 115 ms 4604 KB Output is correct
18 Correct 146 ms 4700 KB Output is correct
19 Correct 112 ms 4692 KB Output is correct
20 Correct 115 ms 4540 KB Output is correct
21 Correct 116 ms 4692 KB Output is correct
22 Correct 668 ms 4692 KB Output is correct