Pair Programming

题目描述

一个程序由一系列指令组成，每条指令属于以下两种形式之一： $\times d$，其中 $d$ 是范围 $[0,9]$ 内的一个数字。 $+s$，其中 $s$ 是表示变量名的字符串。在同一个程序内，所有变量名必须互不相同。 程序执行的结果定义为：从 $0$ 开始，按顺序依次应用每条指令后得到的表达式。例如，执行程序 $[\times 3,+x,+y,\times 2,+z]$ 的结果是表达式 $(0\times 3+x+y)\times 2+z=2\times x+2\times y+z$。不同的程序在执行后可能得到相同的表达式；例如，执行 $[+w,\times 0,+y,+x,\times 2,+z, \times 1]$ 也会得到表达式 $2\times x+2\times y+z$。 Bessie 和 Elsie 各自有一个包含 $N$ 条指令的程序（$1\le N\le 2000$）。她们将把这两个程序交错合并，生成一个长度为 $2N$ 的新程序。注意共有 $\frac{(2N)!}{N!\times N!}$ 种交错方式，但并非所有这些程序在执行后都会产生不同的表达式。 请统计执行 Bessie 和 Elsie 交错后的程序可能产生的不同表达式的数量，并对 $10^9+7$ 取模。 每个输入包含 $T$（$1\le T\le 10$）组测试用例，各测试用例相互独立。保证所有测试用例的 $N$ 之和不超过 $2000$。

输入格式

第一行包含 $T$，表示测试用例数量。 每个测试用例的第一行包含 $N$。 每个测试用例的第二行包含 Bessie 的程序，用一个长度为 $N$ 的字符串表示。每个字符要么是一个数字 $d\in [0,9]$，表示第 1 类指令；要么是字符 $+$，表示第 2 类指令。 每个测试用例的第三行包含 Elsie 的程序，格式与 Bessie 的相同。 在同一个测试用例内，所有指令中的变量名彼此不同。注意并不会给出它们的实际名字，因为它们不影响答案。

输出格式

输出执行 Bessie 和 Elsie 交错后的程序可能产生的不同表达式数量，并对 $10^9+7$ 取模。

4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1

1
3
9
9

提示

对于第一个测试用例，两种可能的交错程序为 $[\times 1, \times 0]$ 和 $[\times 0,\times 1]$。它们在执行后都会产生表达式 $0$。 对于第二个测试用例，交错执行 $[\times 1,\times 2, +x]$ 与 $[+y, \times 0,\times 2]$ 可能产生表达式 $0$、$x$ 或 $2\times x$ 之一。 计分： 输入 2 满足 $N\le 6$。 在输入 3-5 中，所有 $N$ 的总和至多为 $100$。 在输入 6-8 中，所有 $N$ 的总和至多为 $500$。 输入 9-16 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold