CF1776N Count Permutations

给定一个长度为 $n-1$ 的字符串 $s$，其中每个字符都是 $\texttt{}$。 请统计满足如下条件的排列 $p_1,\,p_2,\,\dots,\,p_n$（即 $1,\,2,\,\dots,\,n$ 的一个排列）的个数：对于所有 $i=1,\,2,\,\dots,\,n-1$，如果 $s_i$ 是 $\texttt{}$，则 $p_i > p_{i+1}$。 由于答案可能非常大，请输出其以 $2$ 为底的对数。

第一行包含一个整数 $n$（$2 \le n \le 100\,000$）。 第二行包含一个长度为 $n-1$ 的字符串 $s$，每个字符都是 $\texttt{}$。

输出满足题意的排列个数的以 $2$ 为底的对数。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。形式化地，设你的答案为 $x$，正确答案为 $y$，当且仅当 $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$ 时，答案被接受。

在第一个样例中，只有一个合法的排列，即 $[2, 1]$。因为 $\log_2(1)=0$，所以输出为 $0$。 在第二个样例中，有 $2$ 个合法的排列，分别为 $[3, 1, 2]$ 和 $[2, 1, 3]$。因为 $\log_2(2)=1$，所以输出为 $1$。 在第三个样例中，有 $4$ 个合法的排列，分别为 $[1, 5, 4, 3, 2]$、$[2, 5, 4, 3, 1]$、$[3, 5, 4, 2, 1]$、$[4, 5, 3, 2, 1]$。因为 $\log_2(4)=2$，所以输出为 $2$。 在第四个样例中，有 $909$ 个合法的排列。注意 $\log_2(909)=9.828136484194\ldots$。 由 ChatGPT 4.1 翻译