C++11(clang++ 3.9) 解法, 执行用时: 137ms, 内存消耗: 416K, 提交时间: 2020-07-15 19:01:44

#include<bits/stdc++.h>
using namespace std;
 
const int mod=998244353;
int i,j,n,m,t,ans,A[3005],B[3005],DP[3005];
int fastpow(long long a,int b)
{
    long long s=1;
    for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
    return s;
}
long long C(int n,int m)
{
    return (long long)A[n]*B[m]%mod*B[n-m]%mod;
}
int main()
{
    char R[3005],T[3005];
    for(A[0]=i=1;i<=3000;i++)A[i]=(long long)A[i-1]*i%mod;
    B[3000]=fastpow(A[3000],mod-2);
    for(i=2999;i>=0;i--)B[i]=(long long)B[i+1]*(i+1)%mod;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%s%s",&n,&m,R+1,T+1);
		ans=0,memset(DP,0,sizeof(DP));
        for(i=1;i+m<=n;i++)
        {
            if(R[i]=='0')continue;
            for(j=m;i+j<=n;j++)ans=(ans+C(n-i,j))%mod;
        }
        for(DP[0]=i=1;i<=n;i++)
			for(j=m;j>=1;j--)
			{
				if(R[i]>T[j]&&n-i>=m-j)ans=(ans+DP[j-1]*C(n-i,m-j)%mod)%mod;
				if(R[i]==T[j])DP[j]=(DP[j]+DP[j-1])%mod;
			}
        printf("%d\n",ans);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 276ms, 内存消耗: 101752K, 提交时间: 2020-01-18 15:46:46

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod = 998244353;
const int N = 3010;
int t;
int n,m;
char sn[N],sm[N];
ll cal[N][N];
ll dp[N][N];
void pre()
{
	cal[0][0]=1;
	for(int i=1;i<=3000;i++)
	{
		cal[i][0]=cal[i][i]=1;
		for(int j=1;j<i;j++)
		cal[i][j]=(cal[i-1][j-1]+cal[i-1][j])%mod;
	}
}
int main()
{
	pre();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		scanf("%s",sn+1);
		scanf("%s",sm+1);
		ll ans=0;//用于记录答案
		//计算长度相等的答案 
		dp[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			dp[i][0]=1;
			for(int j=1;j<=m;j++)
			{
				if(sn[i]>sm[j])
				ans=(ans+dp[i-1][j-1]*cal[n-i][m-j]%mod)%mod;
				dp[i][j]=dp[i-1][j];
				if(sn[i]==sm[j])
				dp[i][j]+=dp[i-1][j-1];
				dp[i][j]%=mod;
			}
		}
		//计算长度不相等的答案
		for(int i=1;i<=n;i++)
		{
			if(sn[i]=='0')
			continue;
			for(int j=m;i+j<=n;j++)
			ans=(ans+cal[n-i][j])%mod;
		}
		printf("%lld\n",ans);
	}
}