Mate

题目描述

小 Mate 从他的父母那里得到了一个小写的英文字母组成的一个序列作为礼物。为了让这样一个巧妙的礼物至少有一些用处，他决定在写下一首歌时用它来寻找韵律。

为了找到一个特定的韵律，Mate 想选择一个长度为 $D$ 的单词，且该单词以XY结尾，也就是说，其中倒数第二个字母是 X，最后一个是 Y。Mate 选择单词的过程是，首先划掉给定序列中的一些字母，然后将他没有划掉的字母合并成一个单词。他想知道他可以用多少种不同的方式划掉这些字母，使他满足给定的条件。

如果被划掉的字母的位置的集合不同，则认为两个词的选择是不同的。

题目分析

如上图所示，假设 $x$ 出现在位置 $i$，$y$ 出现在位置 $j$。那么 $x$ 和 $y$ 之间的部分全部删掉，$y$ 之后的部分全部删掉。$x$ 之前的部分保留 $D - 2$ 的元素，所以总共的方案为 $C_{i - 1}^{D - 2}$。

而 $y$ 取位置 $i$ 之后的任意一个 $y$ 均可。假设 $i$ 之后 $y$ 的数量为 $cnt$ 个。那么，固定位置 $i$ 上的 $x$，可能的方案数为 $cnt \times C_{i - 1}^{D - 2}$。

在我的实现中，作了一些预处理。

#include <bits/stdc++.h>
using namespace std;

const int N = 2000 + 5, mod = 1e9 + 7;
char S[N];
int len;
vector<int> pos[30];
int nxt_sum[30][N];

long long C[2005][2005];


int main() {
    // freopen("1.in", "r", stdin);
    cin >> (S + 1);
    len = strlen(S + 1);

    C[0][0] = 1;

    for (int i = 1; i <= len; i++) {
        C[i][0] = 1;

        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            C[i][j] %= mod;
        }
    }

    for (int i = 1; i <= len; i++) {
        pos[S[i] - 'a'].push_back(i);
    }

    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < 26; j++) {
            nxt_sum[j][i] = nxt_sum[j][i + 1];
        }

        nxt_sum[S[i] - 'a'][i]++;
    }

    int q;
    cin >> q;

    while (q--) {
        int d;
        char x, y;
        cin >> d >> x >> y;
        long long ans = 0;

        for (auto i : pos[x - 'a']) {
            ans += C[i - 1][d - 2] * nxt_sum[y - 'a'][i + 1];
            ans %= mod;
        }

        cout << ans << '\n';

    }
}