C++(clang++ 11.0.1) 解法, 执行用时: 513ms, 内存消耗: 17984K, 提交时间: 2022-08-14 10:19:03

#include<bits/stdc++.h>
using namespace std;
const int N=3e3;
const int M=1e8;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,m;
char s[N+5],t[N+5];
struct BigInt{
	int x[N+5];
}dp[N+5];
BigInt operator +(const BigInt& a, const BigInt& b){
	BigInt tmp;
	memset(tmp.x,0,sizeof(tmp.x));
	tmp.x[0]=max(a.x[0],b.x[0]);
	for(int i=1;i<=tmp.x[0];i++){
		tmp.x[i]+=a.x[i]+b.x[i];
		if(tmp.x[i]>=M)tmp.x[i]-=M,tmp.x[i+1]++;
	}
	if(tmp.x[tmp.x[0]+1])tmp.x[0]++;
	return tmp;
}
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>(s+1)>>(t+1);
	for(int i=1;i<=m;i++)
		if(t[i]=='A')t[i]='T';
		else if(t[i]=='T')t[i]='A';
		else if(t[i]=='C')t[i]='G';
		else t[i]='C';
	for(int i=0;i<=m;i++){
		memset(dp[i].x,0,sizeof(dp[i].x));
		dp[i].x[0]=1;
	}
	dp[0].x[1]=1;
	for(int i=1;i<=n;i++)
		for(int j=m;j;j--)
			if(s[i]==t[j])
				dp[j]=(dp[j]+dp[j-1]);
	cout<<dp[m].x[dp[m].x[0]];
	for(int i=dp[m].x[0]-1;i;i--)
		cout<<setw(8)<<setfill('0')<<dp[m].x[i];
	return 0;
}