← 返回题目列表

Codeforces · 1776/N

N. 计数排列

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,长度为 $$$n-1$$$,其字符为 $$$\texttt{<}$$$ 或 $$$\texttt{>}$$$。

计算 $$$1, \, 2, \, \dots, \, n$$$ 的排列 $$$p_1, \, p_2, \, \dots, \, p_n$$$ 使得对于所有 $$$i = 1, \, 2, \, \dots, \, n - 1$$$,如果 $$$s_i$$$ 是$$$\texttt{<}$$$ 则 $$$p_i < p_{i+1}$$$ 并且如果 $$$s_i$$$ 为 $$$\texttt{>}$$$ 则 $$$p_i > p_{i+1}$$$。

由于这个数字可能非常大,请计算其以 $$$2$$$ 为底的对数。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100\,000$$$)。

第二行包含长度为$$$n-1$$$的字符串$$$s$$$; $$$s$$$ 的每个字符都是 $$$\texttt{<}$$$ 或 $$$\texttt{>}$$$。

输出

打印满足语句中描述的约束的排列数的以 $$$2$$$ 为底的对数。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。正式来说,让您的答案为 $$$x$$$,正确答案为 $$$y$$$。当且仅当 $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

2
<

输出 #1

0.0000000000

输入 #2

3
<>

输出 #2

1.0000000000

输入 #3

5
><<<

输出 #3

2.0000000000

输入#4

10
<><<<<<>>

输出#4

9.8281364842

注意

在第一个样本中,只有一个有效排列,即 $$$[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$$$