题目描述

小明是你的好朋友，想和你一起玩密文游戏。你俩约定了一个简单的加密解密方案：字符 0 映射字母 A，字符 1 映射字母 B，依次类推，字符 9 映射字母 J。例如：原文1314的密文为BDBE。

昨天，你给小明发了一条信息。由于未知原因，密文到小明那里发生了缺失。今天上课，你俩见面对照了原文和密文，发现密文丢失了若干字符。设原文S的长度为n，密文T的长度为m，小明突发奇想：对照原文，有多少种方案能把密文补全，字母数量和位置不同，都视为不同的方案。作为好友的你,帮他计算一下吧。

输入格式

第一行，原文S，长度为n(2≤n≤2000)。
第二行，密文T，长度为m(1≤m ≤ n-1 )。

输出格式

一行，所求的方案数。

样例 #1

样例输入 #1

1
2
1414
BE

样例输出 #1

1
3

样例说明

样例中3种补全方案如下。（）中代表所补的密文。
BE(BE)

B(EB)E

(BE)BE

代码长度限制 时间限制 内存限制
16KB 1000ms 2MB

分析

可以看出，本题就是一道方案统计的问题。

一般来说，方案统计的问题也需要借助状态之间的转移，所以我们也总是将这种方案统计的问题与动态规划问题统称为DP，尽管这类问题不涉及最优解。

所以，这个问题我们依旧可以使用之前用来解决动态规划问题的思想，在状态转移的过程中完成对结果方案的统计，即：定状态，找转移，初始化

定状态

对于这个问题，我们可以定义状态：
$$
\begin{vmatrix}
dp[i][j](j\leq i,0\leq i\leq n,0\leq j\leq m) \
n=len(A) \
m=len(B)
\end{vmatrix}
$$
表示$a_1…a_i$与$b_1… b_j$补全匹配的方案数

找转移

定义好了状态，来处理状态间的转移。

可以分成两种情况：
$$
dp[i][j] = \begin{cases}
dp[i - 1][j] & a_i \neq b_j\
dp[i - 1][j - 1]+dp[i - 1][j] & a_i = b_j
\end{cases}
$$

转换成代码即为：

1
2
3
4
5
6
7
8
9
10
//遍历从1开始，0的部分交给初始化
for(int i = 1;i <= n;i++){
	for(int j = 1;j <= m;j++){
		if(a[i] != b[j]){
			dp[i][j] = dp[i - 1][j];
		}else{
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}
}

好了，找到转移方程式之后，下面中要的事情就是要规定初始化，不然从头到尾跑完结果就是0。

一种可行的初始化方案是：$dp[i][0]=1(0≤i≤n)$即对于所有A的前缀序列，不使用B中字符，全部自动补全的方案数是1.

加上初始化后：

1
2
3
4
5
6
7
8
9
10
11
dp[0][0] = 1;
for(int i = 1;i <= n;i++){
	dp[i][0] = 1;
	for(int j = 1;j <= m;j++){
		if(a[i] != b[j]){
			dp[i][j] = dp[i - 1][j];
		}else{
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}
}

边界判断

在dp的过程中，一些状态是不可能出现的，比如超过原序列长度的译码序列.

还有一种情况，由于译码序列需要全部出现在源码序列中，所以译码序列的剩余长度不能超过原序列的剩余长度。

其实上面的条件分别对应着对b枚举的上下边界：

对于j上界，有：$j\leq min(i,m)$

对于j下界，有：$n-i \leq m-j$即$j\geq m-n+i$

加上边界判断：

1
2
3
4
5
6
7
8
9
10
11
dp[0][0] = 1;
for(int i = 1;i <= n;i++){
	dp[i][0] = 1;
	for(int j = max(1,m - n + i);j <= min(i,m);j++){
		if(a[i] != b[j]){
			dp[i][j] = dp[i - 1][j];
		}else{
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
		}
	}
}

答案输出

经过一顿状态转移，易知最终的答案为A序列前n项和B序列前m项的匹配方案:
$$
dp[n][m]
$$

完整代码

初始的代码非常简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
using namespace std;

int n,m;
//产生的情况可能有很大，记得开longlong
long long dp[2005][2005];

int main(){
	string a, b;
	cin >> a >> b;
	n = a.size();
	m = b.size();
	
	for (auto& i:a){
		i = i - '0' + 'A';
	}
	
	dp[0][0] = 1;
	for(int i = 1;i <= n;i++){
		dp[i][0] = 1;
		for(int j = max(1,m - n + i);j <= min(i,m);j++){//注意边界控制 
			if(a[i - 1] == b[j - 1]){
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}else{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	
	cout << dp[n][m];
}

优化
上面虽然解决了题目的核心问题，但是这版代码却是不能够通过的。

最直观的问题就是空间复杂度太高了。还有一些问题就是其可表示的答案范围太小（是的，long long也不够，2000规模的组合结果是非常巨大的数字）

下面就来通过优化算法依次解决这些问题。

为了防止抄袭酿成悲剧，优化部分可能只会展示伪代码。完整的代码会在实验课程时间过后放出。

空间复杂度优化

从题目时空限制来看：

时间限制 内存限制
1000ms 2MB

这道题只给了我们2M的空间。不妨做个粗略的计算，假设这2M的空间全部用来开long long数组，那么我们可以开$2\frac{2^{21}}{8}=2^{18}$ 个数组长度。

而我们仅dp数组就开了$2000*2000=4 \times 10^6 \approx2^{22}$个。

因此这空间是妥妥的超限的，所以我们需要优化算法，将空间复杂度优化到规定一下。

滚动数组优化

让我们将目光聚焦到占据最大空间的dp数组上，再次观察一下转移方程式：
$$
dp[i][j] = \begin{cases}
dp[i - 1][j] & a_i \neq b_j\
dp[i - 1][j - 1]+dp[i - 1][j] & a_i = b_j
\end{cases}
$$
经过观察，可以发现，在转移的过程中，本行的数据仅由前一行的数据转移而来！。

也就是说，如果我们想要的答案在最后一行，那么：仅需要保留正在计算的一行和前一行的数据！

因此这个结论，对于空间优化就存在巨大利好，可以知道：dp数组仅需要开2行

这样以来，我们就将空间复杂度从$O(n^2)$降到了$O(n)$了，肯定可以满足题目的空间需求。

接下来的问题就是：如何使用这两行数组呢？

一个可行方法是每次在第1行计算完值后，将这行值复制到第0行，循环往复。

但是还有一种思路是交替使用两行，每次使用完不需要复制，下次切换到另一行进行求解。

实现也非常简单，可以根据奇偶判断当前使用哪一行

  • 当前行：k = i & 1

  • 上一行：k ^ 1

改造一下之前的dp过程：

1
2
3
4
5
6
7
8
9
10
11
12
dp[0][0] = 1;
for(int i = 1,k;i <= n;i++){
	k = i & 1;
	dp[k][0] = 1;
	for(int j = max(1,m - n + i);j <= min(i,m);j++){//注意边界控制 
		if(a[i] == b[j]){
			dp[k][j] = dp[k ^ 1][j - 1] + dp[k ^ 1][j];
		}else{
			dp[k][j] = dp[k ^ 1][j];
		}
	}
}

最终答案的获取：
$$
dp[n&1][m]
$$

倒序遍历优化

你以为优化到两行就达到最优了？当然不是，我们还可以进行更加**的优化，将转移矩阵优化到一维！

如果在进一步观察我们的转移方程式，可以发现其实对于上一行使用到的项都在j的一边(<=j)。

因此我们不妨直接在原序列上进行迭代，转移方程为：
$$
dp[i][j] = \begin{cases}
dp[j] & a_i \neq b_j\
dp[j - 1]+dp[j] & a_i = b_j
\end{cases}
$$

当然，这里的$dp[j - 1]$应该是上一次计算的值，在计算$dp[j]$之前不应该被改变。

所以不妨倒着枚举j，这样求解过程就可以准确无误的进行了。

其实将转移压缩到一维，连初始化都变得简单了，代码实现：

1
2
3
4
5
6
7
8
9
10
dp[0] = 1;
for(int i = 1;i <= n;i++){
	for(int j = min(i,m);j >= max(1,m - n + i);j--){//注意边界控制 
		if(a[i] == b[j]){
			dp[j] = dp[j - 1] + dp[j];
		}else{
			dp[j] = dp[j];
		}
	}
}

大数运算优化

好了，解决了空间问题，还要解决精度的问题。由于题目的结果非常巨大，连long long的范围也会超出（其实有数百位）。因此我们需要突破long long的限制，手动实现大整数的加法。

封装高精度运算

为了不改变原有的代码，有一个非常不错的想法就是实现一个大整数的类，在其中重载+和整数赋值。然后将dp的数据类型换成这个类。最后，还要能够打印这个数字。

所以，让我们梳理一下这个类型需要的功能：

  • 同类型对象相加运算符重载

  • 整数类型赋值

  • 打印输出

好的，让我们来动手实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct BigInteger{
	int num[300];//10进制下各位的值（倒序存放，便于进位）
	int len;	//数字长度

	BigInteger(){//长度置零，内容置零 
		for(auto& i:num) i = 0;
		len = 0;
	}
	
	int & operator[] (int idx){//重载[]，便于区取数 
		return num[idx];
	}

	BigInteger operator+(BigInteger & o){
		BigInteger ans;
		
		//两个序列叠加 
		for(int i = 0;i < len;i++){
			ans[i] = num[i];
		}
		for(int i = 0;i < o.len;i++){
			ans[i] += o[i];
		}
		
		//整理答案进位 
		ans.len = max(o.len,len);
		for(int i = 0;i < ans.len;i++){
			ans[i + 1] += ans[i] / 10;
			ans[i] %= 10;
		}
		
		//整理最高位进位 
		if(ans[ans.len]){
			ans.len++;
		}

		return ans;
	} 
	
	BigInteger &operator=(int k){
		//倒序拆开赋值 
		len = 0;
		while(k){
			num[len++] = k % 10;
			k /= 10;
		}
		return *this;
	}
	
	void print(){//倒序打印 
		for(int i = len - 1;i >= 0;i--){
			cout << num[i];
		}
	}
}

高精度压位

虽然我们使用高精度模拟大数加减解决了精度问题。但是到了上一步还是不能保证题目能够完美通过。

从时间上说，每次大数运算最长可能达到了数百位的运算，这个常数非常大，在$O(n^2)$的算法复杂度下很有可能超时。

从空间上说，每个dp数组元素都有长达500的高精度数位，其实相当于开了一个2000*500的数组，非常有可能爆空间。

所以我们还要进一步优化（相信我铁汁，这是最后一次！！）

考虑到int能表示的数据范围非常大，而只用它来表示0-9确实有很大浪费。所以我们可以采取高精度压位的操作。

简单来说，就是让高精度数列中的一位表示更多的位数。一位可以表示0-9，也可以表示0-99，也可以表示0-999。区别仅仅是进位时%10，%100，%1000。于是可以将10换成一个基底变量BASE，这个变量是10的幂，几次幂就是表示了几位。

那么这个BASE选多少合适呢？在int下，最大可以选1000000000（10^9）。因为int最大上限为2.1 * 10 ^ 9。所以选择10 ^ 9 刚好可以保证两个数位相加不会溢出！

对于实现，简单修改下之前的代码即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct BigInteger{
	static const int BASE = 1000000000;//基底

	int num[80];//1位表示9位了，80位可以表示720位数
	int len;	//数字长度

	BigInteger() {//默认构造函数，长度置零，内容置零 
        for(auto& i:num) i = 0;
		len = 0;
	}
	
	int & operator[] (int idx) {//重载[]，便于区取数 
		return num[idx];
	}

	BigInteger operator+(BigInteger & o) {
		BigInteger ans;
		
		//两个序列叠加 
		for(int i = 0;i < len;i++) {
			ans[i] = num[i];
		}
		for(int i = 0;i < o.len;i++) {
			ans[i] += o[i];
		}
		
		//整理答案进位 
		ans.len = max(o.len,len);
		for(int i = 0;i < ans.len;i++) {
			ans[i + 1] += ans[i] / BASE ;
			ans[i] %= BASE ;
		}
		
		//整理最高位进位 
		if(ans[ans.len]) {
			ans.len++;
		}

		return ans;
	} 
	
	BigInteger &operator=(int k) {
		//倒序拆开赋值 
		len = 0;
		while(k){
			num[len++] = k % BASE ;
			k /= BASE ;
		}
		return *this;
	}
	
	void print(){//倒序打印 
		//第一位直接输出，后续位需要补0够9位
        cout << num[len-1];
		for(int i = len - 2;i >= 0;i--) {
            cout << setw(9) << setfill('0') << num[i]; // #include <iomanip>
		}
	}
}