题目链接:https://ac.nowcoder.com/acm/contest/885/G
题意:给定字符串s,t,求s中满足字典序大于t的子序列的个数。
思路:组合数学+dp。当子序列长度大于m时很简单,利用初始化的组合数即可。当子序列长度等于m时类似于数位dp的处理办法,我们用dp[pos][num]表示处理到s中的第pos位时已经选择num个数的可能个数。
那么当s[pos]>t[num+1]时:
如果选择s[i]:dp[pos][num]=(dp[pos][num]+C[n-pos][m-num-1])%MOD;
如果不选:dp[pos][num]=(dp[pos][num]+dfs(pos+1,num))%MOD;
当num!=m-1&&s[pos]==t[num+1]时(num!=m-1是因为避免相等的情况,相等时只能不选):
如果选择s[i]:dp[pos][num]=(dp[pos][num]+dfs(pos+1,num+1))%MOD;
如果不选:dp[pos][num]=(dp[pos][num]+dfs(pos+1,num))%MOD;
当s[pos]<t[num+1]:
只能不选:dp[pos][num]=(dp[pos][num]+dfs(pos+1,num))%MOD;
AC代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;typedef long long LL;
const int MOD=;
const int maxn=;int T,n,m;
char s[maxn],t[maxn];
LL ans,C[maxn][maxn],dp[maxn][maxn];void init(){
for(int i = ; i < maxn;++i){
C[i][] = C[i][i] = ;
for(int j = ; j < i;++j){
C[i][j] = C[i-][j] + C[i-][j-];
C[i][j] %= MOD;
}
}
}LL dfs(int pos,int num){
if(num==m) return ;
if(pos>n) return ;
if(dp[pos][num]!=-) return dp[pos][num];
LL tmp=;
if(s[pos]>t[num+])
tmp=(tmp+C[n-pos][m-num-])%MOD;
else if(num!=m-&&s[pos]==t[num+])
tmp=(tmp+dfs(pos+,num+))%MOD;
if(n-pos>=m-num)
tmp=(tmp+dfs(pos+,num))%MOD;
return dp[pos][num]=tmp;
} int main(){
init();
scanf("%d",&T);
while(T--){
ans=;
scanf("%d%d",&n,&m);
scanf("%s",s+);
scanf("%s",t+);
for(int i=;i<=n+;++i)
for(int j=;j<=m;++j)
dp[i][j]=-;
ans=(ans+dfs(,));
for(int i=m+;i<=n;++i)
for(int j=;j<=n-i+;++j)
if(s[j]!='')
ans=(ans+C[n-j][i-])%MOD;
printf("%lld\n",ans);
}
return ;
}