P9657 [ICPC 2021 Macao R] the Matching System

作为安全部门的负责人，你被要求检查公司的一古老匹配系统。 该系统输入两个字符串，一个待匹配字符串和一个模式字符串，并确定前者是否能匹配后者。前者字符串是严格的二进制字符串（即仅包含 $\textbf{0}$ 和 $\textbf{1}$），而后者字符串由四种类型的字符组成：$\textbf{0}$、$\textbf{1}$、$\textbf{*}$ 和 $^$，其中 $\textbf{*}$ 表示匹配零个或多个任意二进制字符，$^$ 表示匹配恰好一个二进制字符。 该系统有两种匹配方法：最大匹配和最小匹配。 考虑两个字符串的起始位置。最大匹配方法将根据模式字符串的当前字符做出不同的决定： - $\textbf{*}$: 系统将从 $L$ 到 $0$ 枚举 $i$，其中 $L$ 是待匹配字符串的剩余长度。在每次枚举开始之前，系统消耗 1 单位的能量。然后它暂时假设模式字符串中的当前 $\textbf{*}$ 匹配待匹配字符串中的连续 $i$ 个字符，并尝试递归地匹配两个字符串的剩余位置。只要有一次尝试成功，系统将放弃剩余的枚举并停止整个系统。否则，它将尝试下一个枚举，直到所有尝试都被尝试完毕，最后返回到先前的 $\textbf{*}$ 枚举。 - $\textbf{0,1}$: 如果待匹配字符串已经耗尽，系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它消耗 $1$ 单位的能量来比较模式字符串和待匹配字符串之间的当前字符。如果结果相同，它将继续分析这两个字符串的剩余位置，否则返回到先前的 $\textbf{*}$ 枚举。 - $^$: 如果待匹配字符串已经耗尽，系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它消耗 $1$ 单位的能量并继续分析两个字符串。 当模式字符串耗尽时，系统将同时检查待匹配字符串。如果待匹配字符串也已经耗尽，系统将返回“是”并停止整个过程，否则，它将返回到先前的 $\textbf{*}$ 枚举。在尝试了所有尝试并找不到匹配方法后，系统最终将返回“否”。 最小匹配执行类似的操作，除了 $\textbf{*}$ 的枚举顺序（即从 $0$ 到 $L$ 枚举 $i$）。 这两种匹配方法似乎不太有效，所以你想黑掉它们。请为每种匹配方法构造一个长度为 $n$ 的模式字符串和待匹配字符串，使得系统返回“是”，能量消耗尽可能大。

每个测试文件中只有一个测试用例。 第一行仅包含一个整数 $n$（$1 \le n \le 10^3$），表示需要构造的字符串的长度。

请输出最大匹配方法的模式字符串、待匹配字符串和能量消耗的前 $3$ 行。然后输出最小匹配方法的模式字符串、待匹配字符串和能量消耗的后 $3$ 行。 如果有多种构造方式，你可以输出任何一种。 能量消耗可能非常大，所以你需要输出取模 $(10^9+7)$ 后的值。请注意，这仅供你方便，你需要在取模之前最大化能量消耗。

题目描述 作为安全部门的负责人，你被要求检查公司的一古老匹配系统。 该系统输入两个字符串，一个待匹配字符串和一个模式字符串，并确定前者是否能匹配后者。前者字符串是严格的二进制字符串（即仅包含 $\textbf{0}$ 和 $\textbf{1}$），而后者字符串由四种类型的字符组成：$\textbf{0}$、$\textbf{1}$、$\textbf{*}$ 和 $^$，其中 $\textbf{*}$ 表示匹配零个或多个任意二进制字符，$^$ 表示匹配恰好一个二进制字符。 该系统有两种匹配方法：最大匹配和最小匹配。 考虑两个字符串的起始位置。最大匹配方法将根据模式字符串的当前字符做出不同的决定： - $\textbf{*}$: 系统将从 $L$ 到 $0$ 枚举 $i$，其中 $L$ 是待匹配字符串的剩余长度。在每次枚举开始之前，系统消耗 1 单位的能量。然后它暂时假设模式字符串中的当前 $\textbf{*}$ 匹配待匹配字符串中的连续 $i$ 个字符，并尝试递归地匹配两个字符串的剩余位置。只要有一次尝试成功，系统将放弃剩余的枚举并停止整个系统。否则，它将尝试下一个枚举，直到所有尝试都被尝试完毕，最后返回到先前的 $\textbf{*}$ 枚举。 - $\textbf{0,1}$: 如果待匹配字符串已经耗尽，系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它消耗 $1$ 单位的能量来比较模式字符串和待匹配字符串之间的当前字符。如果结果相同，它将继续分析这两个字符串的剩余位置，否则返回到先前的 $\textbf{*}$ 枚举。 - $^$: 如果待匹配字符串已经耗尽，系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它消耗 $1$ 单位的能量并继续分析两个字符串。 当模式字符串耗尽时，系统将同时检查待匹配字符串。如果待匹配字符串也已经耗尽，系统将返回“是”并停止整个过程，否则，它将返回到先前的 $\textbf{*}$ 枚举。在尝试了所有尝试并找不到匹配方法后，系统最终将返回“否”。 最小匹配执行类似的操作，除了 $\textbf{*}$ 的枚举顺序（即从 $0$ 到 $L$ 枚举 $i$）。 这两种匹配方法似乎不太有效，所以你想黑掉它们。请为每种匹配方法构造一个长度为 $n$ 的模式字符串和待匹配字符串，使得系统返回“是”，能量消耗尽可能大。 输入格式 每个测试文件中只有一个测试用例。 第一行仅包含一个整数 $n$（$1 \le n \le 10^3$），表示需要构造的字符串的长度。 输出格式 请输出最大匹配方法的模式字符串、待匹配字符串和能量消耗的前 $3$ 行。然后输出最小匹配方法的模式字符串、待匹配字符串和能量消耗的后 $3$ 行。 如果有多种构造方式，你可以输出任何一种。 能量消耗可能非常大，所以你需要输出取模 $(10^9+7)$ 后的值。请注意，这仅供你方便，你需要在取模之前最大化能量消耗。 翻译来自于：[ChatGPT](https://chatgpt.com/)。 题面翻译由 ChatGPT-4o 提供。