Submission #239021

#	Time	Username	Problem	Language	Result	Execution time	Memory
239021		NONAME	Mate (COCI18_mate)	C++17	100 / 100	382 ms	32560 KiB

mate

#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 / 100