2019牛客暑期多校训练营（第五场） G.subsequence 1 （dp）

题目链接

大意：给你两个字符串a,b，问你第一个字符串有多少子序列的十进制表示大于第二个字符串的十进制表示
思路：考虑 $dp$dp
$dp\left[i\right]\left[\right[0]表示a字符串中长度为i的子序列等于b的个数$dp[i][[0]表示a字符串中长度为i的子序列等于b的个数
$dp\left[i\right]\left[\right[1]表示a字符串中长度为i的子序列大于b的个数$dp[i][[1]表示a字符串中长度为i的子序列大于b的个数
$dp\left[i\right]\left[\right[2]表示a字符串中长度为i的子序列小于b的个数$dp[i][[2]表示a字符串中长度为i的子序列小于b的个数
然后枚举每个a字符串的字符转移即可。

#include<bits/stdc++.h>
 
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
using namespace std;
 
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
const LL mod=998244353;
int t,n,m;
char a[N],b[N];
LL dp[3333][3],p[3333][3];
int main(){
    ios::sync_with_stdio(false);
    for(cin>>t;t;t--){
        cin>>n>>m;
        cin>>a+1>>b+1;
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++)p[j][0]=dp[j][0],p[j][1]=dp[j][1],p[j][2]=dp[j][2];
            for(int j=1;j<=i;j++){
                if(a[i]=='0'&&j==1)continue;
                if(j<=m){
                    if(b[j]==a[i]){dp[j][0]+=p[j-1][0],dp[j][1]+=p[j-1][1];dp[j][2]+=p[j-1][2];}
                    else if(a[i]>b[j])dp[j][1]+=p[j-1][0]+p[j-1][1],dp[j][2]+=p[j-1][2];
                    else dp[j][2]+=p[j-1][0]+p[j-1][2],dp[j][1]+=p[j-1][1];
                    dp[j][0]%=mod;
                    dp[j][1]%=mod;                 
                    dp[j][2]%=mod;
                }else{
                    dp[j][1]+=p[j-1][0]+p[j-1][1]+p[j-1][2];
                    dp[j][1]%=mod;
                }
            }
        }
        LL ans=0;
        for(int i=m;i<=n;i++){
            ans+=dp[i][1];
            ans%=mod;
        }
        cout<<ans<<endl;
    }
 
    return 0;
}