这道题挺水的。

首先，这道题肯定是一个普及的二维线性 dp。

设 $dp_{i,j}$ 位 $S$ 前 $i$ 位与 $T$ 前 $j$ 位匹配的方案数。

初始条件 $dp_{0,0}=dp_{i,0}=1$。

然后对于每一位 $j$，我们可以选择在前面插入一位来匹配 $i$，如果能匹配，还可以选择自己去匹配 $i$。

所以如果 $S_i$ 能匹配 $T_j$，那么 $dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}$。

否则，$dp_{i,j}=dp_{i-1,j}$。

然后没有取模，来个高精度。

结果发现爆空间，来个滚动数组就做完了。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int a[310];
	int len;
	node(int x=0){
		memset(a,0,sizeof a);
		for(len=1;x;len++) a[len]=x%10,x/=10;
		len--;
	}
	int &operator [] (int i){return a[i];}
	void fl(int l){
		len=l;
		for(int i=1;i<=len;i++) a[i+1]+=a[i]/10,a[i]%=10;
		for( ;!a[len]; ) len--;
	}
};
inline void print(node x){
	for(int i=max(1,x.len);i>=1;i--)
		cout<<x[i];
	cout<<"\n";
}
inline node operator + (node x,node y){
	node c;
	c.len=max(x.len,y.len);
	for(int i=1;i<=c.len;i++)
		c[i]=x[i]+y[i];
	c.fl(c.len+2);
	return c;
}
node dp[2][2010];
int n,m;
string s,t;
char npy[130];
int main() {
	cin>>n>>m>>s>>t,s=" "+s,t=" "+t;
	dp[0][0]=1; 
	npy['A']='T',npy['T']='A',npy['C']='G',npy['G']='C';
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++){
			dp[i&1][j]=dp[(i&1)^1][j];
			if(npy[s[i]]==t[j]) dp[i&1][j]=dp[i&1][j]+dp[(i&1)^1][j-1];
		}
	print(dp[n&1][m]); 
	return 0;
}