CF567F Mausoleum

伯兰德的国王 Berl IV 最近去世了。致敬 Berl V！作为对已故国王最高成就的象征，新国王决定在首都的主广场为 Berl IV 建造一座陵墓。 陵墓将由 $2n$ 块积木建成，每块都是长方体。这些积木的底部都是 $1\times 1$ 米的正方形。在这些积木中，恰好有两块高为 $1$ 米，恰好有两块高为 $2$ 米，……，恰好有两块高为 $n$ 米。 这些积木会首尾相连地排成一排，之间不会有空隙。当然，并不是所有的积木排列方式都能形成一座陵墓。为了让排列满足“陵墓”形式，必须满足：从一头走到另一头的过程中，积木的高度要先不下降（即递增或保持不变），然后不上升（递减或保持不变）。这两个区域有可能被省略。例如，以下积木高度序列都满足要求： - $[1,2,2,3,4,4,3,1]$； - $[1,1]$； - $[2,2,1,1]$； - $[1,2,3,3,2,1]$。 突然，出现了 $k$ 个额外的限制条件。每个条件形式如下：“$h[x_{i}]$ sign $ _{i}$ $h[y_{i}]$”，其中 $h[t]$ 表示第 $t$ 块积木的高度，$sign_{i}$ 是五种关系符号之一：'='（等于）、''（大于）、'='（大于等于）。因此，第 $k$ 个附加条件通过一对下标 $x_{i}$，$y_{i}$（$1\leq x_{i}, y_{i} \leq 2n$）和关系符号 $sign_{i}$ 给出。 计算有多少种不同的排列方式，既满足“陵墓”形状的要求（见第 3 段），又满足全部 $k$ 个额外要求。

输入的第一行为两个整数 $n$ 和 $k$（$1 \leq n \leq 35$，$0 \leq k \leq 100$），分别表示积木对数和附加要求的数量。 接下来的 $k$ 行，每行给出一个额外要求，格式为 "$x_{i}$ $sign_{i}$ $y_{i}$"（$1\leq x_{i}, y_{i} \leq 2n$），$sign_{i}$ 为五种关系符号之一。

输出满足条件的排列方式总数。

由 ChatGPT 5 翻译