oj.uz

Submission #239021

# Submission time Handle Problem Language Result Execution time Memory
239021 2020-06-14T07:04:46 Z NONAME Mate (COCI18_mate) C++17
100 / 100
 382 ms 32560 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

const int N = 2e5 + 10;
const int base = 1e9 + 7;

string s;
int c[2500][2500], res[2500][2500], res0[26][2500], sf[2500][26];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("in.txt", "r", stdin);

    cin >> s;
    int n = int(s.size());

    for (int i = 0; i < 2500; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % base;
    }

    for (int i = n - 1; i >= 0; --i)
    for (int j = 0; j < 26; j++) {
        sf[i][j] = (i + 1 == n ? 0 : sf[i + 1][j]);

        sf[i][j] += (s[i] == (j + 'a'));
    }

    for (int i = 0; i < n; ++i) {
        char c1 = s[i];

        for (int j = 0; j < 26; ++j)
        for (int l = -1; l < i; ++l) {
            int v = (c1 - 'a' + 1) + 29 * (j + 1);

            int vl = sf[i][j] - ((c1 - 'a') == j);

            res[v][l + 1] = (res[v][l + 1] + ((c[i][l + 1] * 1ll * vl) % base)) % base;
        }
    }

//    for (int i = 0; i < n; ++i)
//    for (int j = i + 1; j < n; ++j) {
//        char c1 = s[i], c2 = s[j];
//        int v = (c1 - 'a' + 1) + 29 * (c2 - 'a' + 1);
//
//        for (int l = -1; l < i; ++l)
//            res[v][l + 1] = (res[v][l + 1] + c[i][l + 1]) % base;
//    }

    int q;
    cin >> q;
    while (q--) {
        int d;
        string t;
        cin >> d >> t;

        cout << res[(t[0] - 'a' + 1) + 29 * (t[1] - 'a' + 1)][d - 2] << "\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23168 KB Output is correct
2 Correct 24 ms 22912 KB Output is correct
3 Correct 24 ms 23040 KB Output is correct
4 Correct 27 ms 23040 KB Output is correct
5 Correct 55 ms 24568 KB Output is correct
6 Correct 56 ms 24696 KB Output is correct
7 Correct 49 ms 24568 KB Output is correct
8 Correct 46 ms 24440 KB Output is correct
9 Correct 382 ms 32312 KB Output is correct
10 Correct 376 ms 32560 KB Output is correct