题解 | #[JLOI2011]基因补全#

时间复杂度约为O（mn）（包含高精度运算，实际为 O(mnl) l为大数的平均长度）

算法思想：使用一维数组以动态规划形式从单字符子串开始计算可能数，同时计1为计算边界，因为题目并不要求取余，但是2000！很明显超过常用数据类型上限，所以使用大数加法用于计算。详细可见代码。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> add(const vector<int>& a, const vector<int>& b) {
    vector<int> res;
    int carry = 0;
    size_t i = 0;
    while (i < a.size() || i < b.size() || carry) {
        int sum = carry;
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        res.push_back(sum % 10);
        carry = sum / 10;
        ++i;
    }
    return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    
    vector<char> str1, str2;
    
    for(int i = 0; i < n;i++){
    	char temp;
		cin >> temp;
		switch(temp){
			case 'A':temp = 'T';break;
			case 'G':temp = 'C';break;
			case 'C':temp = 'G';break;
			case 'T':temp = 'A';break;
		}
		str1.push_back(temp);
	}
    
    for(int i = 0; i < m;i++){
    	char temp;
		cin >> temp;
		str2.push_back(temp);
	}
	
	vector<vector<int>> dp(m+1, vector<int>());
	dp[0] = {1};
	
	for(char s : str1){
		for(int i = m; i >= 1;i--){
			if(str2[i - 1] == s){
				dp[i] = add(dp[i], dp[i - 1]);
			}
		}
	}
	
	for(int i = dp[m].size();i > 0;i--){
		cout << dp[m][i - 1];
	}
}