自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 22:37:33，当前版本为作者最后更新于2022-06-06 15:02:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到数据范围再考虑到 USACO 从不卡常，可以猜想这应该是个 $O(N^2)$ 的 DP。

首先对输入串做一个处理：如果有乘 $0$ 的操作，那前面就没用了，如果有乘 $1$ 的操作，对答案没有影响，直接舍去。

小学数学里有乘法交换律和加法交换律： $a\cdot b = b \cdot a,a + b = b + a$ ，也就是说，如果两个同类操作放在一起，那么交换它们产生的结果不变。

定义一种对 $(x,y)$ ， 其中 $x$ 是来自 $A$ 的操作， $y$ 是来自 $B$ 的操作，且操作类型相同。

那么答案是不包含这类对 $(x,y)$ 的串的数量，因为出现这种情况的时候把 $x,y$ 交换，直到没有这种对后，表达式的结果不变。

设 $f[i][j][0/1]$ 表示 $A$ 串匹配到 $i$ 位，$B$ 串匹配到 $j$ 位，最后一个是 $A$ 或者 $B$ 的指令的答案。

对于结尾为 $0$ 的情况： $f[i+1][j][0] = f[i][j][0]+f[i][j][1]$ ：因为这些串都合法，所以在后面插入一个新的来自 $A$ 的操作的新串不会不合法。

对于结尾为 $1$ 的情况 ： 如果是 $A_i \neq B_{j+1}$ ，则 $f[i][j+1][1]=f[i][j][0]+f[i][j][1]$ ，否则 $f[i][j+1][1]=f[i][j][1]$ 。

边界条件： $f[0][0][1] = 1$ ，虽然没有具体意义，但只有最后一维是 $1$ 才能合法的开始转移，或者手推也行（只不过我比较懒）。

UPDATE ：去了 memset 以后，跑的飞快，一发卡进最优解。

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, mod = 1e9 + 7;
int n, f[N][N][2], lena, lenb, T;
char str[N], a[N], b[N];
inline void read(char s[], int &slen) {
	slen = 0;
	cin >> str;
	int len = strlen(str);
	for(int i = 0; i < len; i++) {
		if(str[i] == '0') slen = 0;
		else if(str[i] == '1') continue;
		if(str[i] != '+') str[i] = '*';
		s[++slen] = str[i];
	}
}
inline int add(int a, int b) {
	a += b;
	return a >= mod ? a - mod : a;
}
signed main() {
	ios::sync_with_stdio(false);
	cin >> T;
	while(T--) {
		cin >> n;
		read(a, lena), read(b, lenb);
		f[0][0][1] = 1;
		for(int i = 0; i <= lena; i++) {
			for(int j = 0; j <= lenb; j++) {
				if(i < lena) f[i + 1][j][0] = add(f[i][j][0], f[i][j][1]);
				if(j < lenb) f[i][j + 1][1] = f[i][j][1];
				if(i > 0 && j < lenb && a[i] != b[j + 1]) f[i][j + 1][1] = add(f[i][j + 1][1], f[i][j][0]);
			}
		}
		printf("%d\n", add(f[lena][lenb][0], f[lena][lenb][1]));
	}
	return 0;
}