C++(clang++ 11.0.1) 解法, 执行用时: 110ms, 内存消耗: 63396K, 提交时间: 2022-12-06 12:05:34

#include<stdio.h>
#include<string.h>
const int mo=998244353;
char a[3010],b[3010];
int c[3010][3010],dp[3010][3010];
int main(){
	int t,n,m,i,j;
	scanf("%d",&t);
	for(i=0;i<=3000;i++)
	{
		c[i][0]=1;
		for(j=1;j<=i;j++)
		c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
	}
	while(t--)
	{
		scanf("%d%d",&n,&m);
		scanf("%s%s",a+1,b+1);
		long long ans=0;
		for(i=1;i<=n;i++)
		if(a[i]!='0')
		for(j=m;j<=n-i;j++)
		(ans+=(c[n-i][j]))%=mo;
		for(i=0;i<=n;i++)
		for(j=0;j<=m;j++)
		dp[i][j]=0;
		dp[0][0]=1;
		for(i=1;i<=n;i++)
		{
			dp[i][0]=1;
			for(j=1;j<=m;j++)
			{
				dp[i][j]=dp[i-1][j];
				if(a[i]==b[j])
				(dp[i][j]+=dp[i-1][j-1])%=mo;
				else if(a[i]>b[j])
				ans=(ans+1ll*dp[i-1][j-1]*c[n-i][m-j])%mo;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 250ms, 内存消耗: 117576K, 提交时间: 2019-08-02 11:11:16

#include <bits/stdc++.h>
#define rep(i, a, b) for (register int i = a; i <= b; i++)
using namespace std;
typedef long long ll;
const int mod = 998244353;

ll a[3010][3010];
int n,m;
char s[3010],t[3010];
ll ans=0;
ll dp[3010][3010];
int main() {
	int T;
	cin>>T;
	a[0][0]=1;
	rep(i,1,3005)rep(j,0,i)a[i][j]=(a[i-1][j-1]+a[i-1][j])%mod;
	while(T--){
		cin>>n>>m;
		cin>>s>>t;
		ans=0;
		rep(i,0,n-m-1)if(s[i]!='0')rep(j,m,n-i-1)ans=(ans+a[n-i-1][j])%mod;
		rep(i,0,n)rep(j,0,m)dp[i][j]=0;
		for(int j=m-1;j>=0;j--){
			for(int i=n-m+j;i>=0;i--){
				if(s[i]==t[j])
					dp[i][j]=dp[i+1][j+1];
				else if(s[i]>t[j])
					dp[i][j]=a[n-i-1][m-j-1];
				dp[i][j]=(dp[i][j]+dp[i+1][j])%mod;
			}
		}
		cout<<(ans+dp[0][0])%mod<<endl;
	}
	return 0;    
}