牛客多校第五场

https://ac.nowcoder.com/acm/contest/885#question

G

题意：给a,b两个字符串问，a串中有多少子序列所对饮的数字大于b串所对饮的长度。

思路：这个我觉得真是一个牛逼题，比赛我几个小时没想出来。分两种情况，a串中长度比b大的子序列和a串中长度等于b的长度但比b大的子序列，第一种情况比赛时随便搞，但难就难在第二种上了，

第二种需要先预处理一个数组c(i,j)用来表示一个字符串长度为i，所包含所有的长度为j的子序列有多少个，之后我设了一个DP状态f(i,j)表示a串的后缀到i（即i~n这个区间）的子序列中长度为j且大于b串后缀到j（即j~m这个区间）所代表的数字的子序列的个数。 然后我就从后往前枚举a串的每个数字，与b串的每位的数字做比较。两种情况：1.如果ai=bj,f[i][j]=f[i+1][j+1]，表示如果相等，那么可以从前一个长度的合法子序列取ai这个数字，2.如果ai>bi.f[i][j]=c[n-i][m-j]表示，如果ai大的话，那么以ai作为开头,长度为m-j的子序列的都可以取,然后数量就是c[n-i][m-j]，因为这时a后缀串中只有n-i个字符串。

然后注意预处理数组时下标从0开始赋值

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
const int mod=998244353;
#define ll long long
int c[maxn][maxn];
int f[maxn][maxn];
char a[maxn],b[maxn];
void per()
{
    for(int i=0; i<=3000; i++)
    {
        c[i][0]=1;
        for(int j=1; j<=i; j++)
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    per();
//    for(int i=1;i<=15;i++)
//    {
//        for(int j=1;j<=15;j++)
//            printf("%d ",c[i][j]);
//        printf("
");
//    }
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        scanf("%s",a+1);
        scanf("%s",b+1);
        ll ans=0;
        for(int i=1; i<=n-1; i++)
        {
            if(a[i]!='0')
                for(int j=m; 1+j<=n; j++)
                    ans=(ans+c[n-i][j])%mod;
        }
        for(int i=1; i<=n+1; i++)
            for(int j=1; j<=m+1; j++)
                f[i][j]=0;
        for(int i=n; i>=1; i--)
        {
            for(int j=m; j>=1; j--)
            {
                f[i][j]=f[i+1][j];
                if(a[i]==b[j]) f[i][j]=(f[i][j]+f[i+1][j+1])%mod;
                if(a[i]>b[j]) f[i][j]=(f[i][j]+c[n-i][m-j])%mod;
            }
        }
        ans=(ans+f[1][1])%mod;
        printf("%lld
",ans);
    }
}