题解：P4958 [COCI 2017/2018 #6] Mate

jiangjiangQwQ · 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;
}