自动搬运

查看原文

来自洛谷，原作者为

	jiangjiangQwQ 加油！勇夺第二吧各位。

搬运于2025-08-24 22:05:40，当前版本为作者最后更新于2025-07-17 15:51:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

枚举字符 $X$ 和 $Y$ 在原字符串中的出现位置分别为 $i$ 和 $j$。那么在答案中 $i=D-1$ 且 $j=D$，中间字符均删除，并在 $i$ 前面保留 $D-2$ 个字符。显然只有当 $i\geq D-2$ 时才能使得 $i,j$ 成为一组合法解。保留字符的方案数为 $\binom{i-1}{D-2}$，直接统计就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2005,Mod=1e9+7;
string s;
int q,d,sy[N][26];
char x,y;
int f[N][N];
int C(int n,int m){
    return f[n][m];
}int g[N][26][26];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s>>q;
    int n=s.size();
    f[0][0]=1;
    for(int i=1;i<n;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%Mod;
        }
    }memset(g,-1,sizeof g);
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++){
            sy[i][j]=sy[i+1][j]+(s[i]-'a'==j);
        }
    }
    while(q--){
        cin>>d>>x>>y;
        if(~g[d][x-'a'][y-'a']){cout<<g[d][x-'a'][y-'a']<<'\n';continue;}
        int ans=0;
        for(int i=0;i<n;i++){
            if(s[i]==x&&d-2<=i){
                int sumy=sy[i+1][y-'a'];
                // cout<<i<<' '<<sumy*C(i,d-2)%Mod<<'\n';
                ans=(ans+sumy*C(i,d-2)%Mod)%Mod;
            }
        }cout<<(g[d][x-'a'][y-'a']=ans)<<'\n';
    }
    return 0;
}