---

layout: post

title: 2019牛客暑期多校训练营（第五场）G - subsequeue 1 (一题我真的不会的题)

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- ACM-ICPC

---

题意

给你两个由数字组成的字符串\(S\),\(T\) 长度为\(1e3\)，问你S中有多少个子序列的值大于字符串T；

思路

首先在比赛的时候一眼确定是\(N^2\) 复杂度的DP，但是想了两三个小时却没想到怎么转移，各种构造\(dp[i][j]\)的含义。可是无功而返。

比赛结束后发现大家都用到了组合数。发现大家这题都用分两类来讨论做题。这时候才焕然大悟。

原来比T大的字符串可以分成两类根本不用瞎几把转移。

于是这题的解法很快就想到了，如果是大于的情况，那么只要第一个字符不是0，那么后面的几个字符串就随便取就行了。

大于的结束了接下来就是相等的情况。如果相等 那么肯定要考虑是从\(S\)串的哪个作为起点来构造子序列。并且这个S串的起点，的下一个点从哪里转移。这些都是可以DP的。于是我们基本的状态确定了，我们首先要确定目前构造到S串的哪个位置了。同时这个位置对于着T串的哪个位置，这样我们就可以开始转移。

#include<bits/stdc++.h>

using namespace std;

const int maxn=4e3+50;

typedef long long ll;

const ll mod=998244353;

ll dp[maxn][maxn];

ll C[maxn][maxn];

void add(ll &a,ll b){

    a+=b;

    if(a>=mod)a-=mod;

}

char s[maxn],t[maxn];

int main(){

    std::ios::sync_with_stdio(false);

    int T;

    C[0][0]=1;

    for(int i=1;i<=3000;i++){

        for(int j=0;j<=i;j++){

            if(j==0||j==i)C[i][j]=1;

            else add(C[i][j],C[i-1][j-1]+C[i-1][j]);

        }

    }

    cin>>T;

    while(T--){

        int n,m;

        cin>>n>>m;

        cin>>s+1>>t+1;

        for(int i=0;i<=n+10;i++){

            for(int j=0;j<=m+10;j++)dp[i][j]=0;

        }

        ll ans=0;

        for(int i=1;i<=n;i++){

            if(s[i]=='0')continue;

            for(int j=m;j<=n;j++){

                add(ans,C[n-i][j]);

            }

        }

        ///dp[i][j]= 从后往前到当前S串第j的字符位置匹配到T串的第I个字符并且大于的个数

        for(int i=m;i;i--){

            for(int j=n;j;j--){

                dp[j][i]=dp[j+1][i];  ///因为包括了没有第j个字符的情况，所以如果第j+1个字符符合条件也可以

                if(t[i]==s[j])add(dp[j][i],dp[j+1][i+1]);

                /// 如果两个字符相同 那么答案就是少取这第J个字符同时还大于的数量

                if(t[i]<s[j])add(dp[j][i],C[n-j][m-i]);

                ///如果大于  那么答案就是后面的几个随便取几个就行了。

            }

        }

        cout<<(ans+dp[1][1])%mod<<endl;

    }

    return 0;

}