CF1937B Binary Path
题目描述
给你一个 $2 \times n$ 的网格，网格中填有 $0$ 和 $1$。第 $i$ 行第 $j$ 列的数字记为 $a_{ij}$。
有一只蚂蚱位于左上角的格子 $(1, 1)$，它每次只能向右或向下跳一格。它想要到达右下角的格子 $(2, n)$。请考虑沿路径经过的格子中数字按顺序组成的长度为 $n+1$ 的二进制字符串。
你的目标是：
1. 找出通过任意可行路径能够得到的字典序最小的字符串；
2. 计算有多少条路径能够得到这个字典序最小的字符串。
$^\dagger$ 如果两个字符串 $s$ 和 $t$ 长度相同，$s$ 的字典序小于 $t$，当且仅当在第一个不同的位置，$s$ 的字符小于 $t$ 的对应字符。
输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。
第二行包含一个长度为 $n$ 的二进制字符串 $a_{11} a_{12} \ldots a_{1n}$（$a_{1i}$ 为 $0$ 或 $1$）。
第三行包含一个长度为 $n$ 的二进制字符串 $a_{21} a_{22} \ldots a_{2n}$（$a_{2i}$ 为 $0$ 或 $1$）。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每组测试用例，输出两行：
1. 第一行输出通过任意可行路径能够得到的字典序最小的字符串；
2. 第二行输出能够得到该字符串的路径数量。
说明/提示
在第一个测试用例中，字典序最小的字符串是 $\mathtt{000}$。有两条路径可以得到这个字符串：
在第二个测试用例中，字典序最小的字符串是 $\mathtt{11000}$。只有一条路径可以得到这个字符串：
由 ChatGPT 4.1 翻译