subsequence 1（牛客多校第五場）

subsequence 1

本題大意：給出兩個序列s和t，然後計算存在多少s的子序列為正整數的時候值大于t

本題可以想到，當s的子序列的長度大于t的時候那麼肯定值比他大，當s的子序列的長度小于t的時候，那麼肯定比t小，是以總情況可以分為兩種，一種是子序列長度大于t的時候可以通過組合數來解決，當子序列長度等于t的時候則可以通過dp解決，設立dp[i][j]表示當到s的第i個字元的時候，已經有j個字元與t相同的情況，然後挨個周遊i和j，注意好細節即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN=3005;
const int mod=998244353;
ll c[MAXN][MAXN],dp[MAXN][MAXN],ans;
char s[MAXN],pp[MAXN];
int t,n,m;
void init()//組合數函數
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for(int i=2; i<=3000;i++)
    {
        c[i][0]=1;
        for(int j=1; j<=i; j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
}
int main()
{
    init();
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        scanf("%s%s",s+1,pp+1);//将s和t都處理成從1開始友善dp
        for(int i=1; i<=n-m; i++)
            if(s[i]!='0')
                for(int j=m; j<=n-i; j++)//挨個周遊s的每一位，當s[i]不為0的時候就從加上組合數，
                    ans=(ans+c[n-i][j])%mod;//看不太懂可以在紙上找個樣例試一試
        for(int i=0; i<=n; i++)
            dp[i][0]=1;//處理每一種0位相同的情況為1
        for(int i=1; i<=n; i++)
            for(int j=1; j<=min(m,i); j++)
            {
                dp[i][j]=dp[i-1][j];
                if(s[i]==pp[j])
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;//如果相同，那就從dp[i-1][j-1]加上去，因為位數加了一位，相同位數也加了一位
                else if(s[i]>pp[j])
                    ans=(ans+dp[i-1][j-1]*c[n-i][m-j])%mod;//大于的話就可以直接從s剩下的字元中挑m-j個出來，還是組合數
            }
        printf("%lld\n",ans);
    }
    return 0;
}