제출 #1168564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168564		trufanov.p	Mate (COCI18_mate)	C++20	100 / 100	188 ms	38684 KiB

mate

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>

using namespace std;

#pragma GCC optimize("O3")
//#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

const ll Mod = 1e9 + 7;

inline ll add(ll a, ll b, ll Mod) {
    return (a + b < Mod ? a + b : a + b - Mod);
}

inline ll mul(ll a, ll b, ll Mod) {
    return (a * b) % Mod;
}

const int SIZE = 2005;

ll cnt[26][26][SIZE];
ll C[SIZE][SIZE];

void precalc() {
    C[0][0] = 1;
    for (int i = 1; i < SIZE; ++i) {
        C[i][0] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = add(C[i - 1][j - 1], C[i - 1][j], Mod);
        }
        C[i][i] = 1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    precalc();
    string s;
    cin >> s;
    int n = s.size();
    vector<int> cntsuff(26);
    for (int i = n - 1; i > -1; --i) {
        for (int y = 0; y < 26; ++y) {
            if (cntsuff[y] == 0) {
                continue;
            }
            for (int len = 2; len <= i + 2; ++len) {
                cnt[s[i] - 'a'][y][len] = add(cnt[s[i] - 'a'][y][len], mul(cntsuff[y], C[i][len - 2], Mod), Mod);
            }
        }
        cntsuff[s[i] - 'a']++;
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int len;
        char x, y;
        cin >> len >> x >> y;
        cout << cnt[x - 'a'][y - 'a'][len] << '\n';
    }
}

• Subtask 1: 100 / 100