Count Permutations

题目描述

You are given a string $ s $ with length $ n-1 $ whose characters are either $ \texttt{<} $ or $ \texttt{>} $ . Count the permutations $ p_1, \, p_2, \, \dots, \, p_n $ of $ 1, \, 2, \, \dots, \, n $ such that, for all $ i = 1, \, 2, \, \dots, \, n - 1 $ , if $ s_i $ is $ \texttt{<} $ then $ p_i < p_{i+1} $ and if $ s_i $ is $ \texttt{>} $ then $ p_i > p_{i+1} $ . Since this number can be very large, compute its logarithm in base $ 2 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 100\,000 $ ). The second line contains a string $ s $ of length $ n-1 $ ; each character of $ s $ is either $ \texttt{<} $ or $ \texttt{>} $ .

输出格式

Print the logarithm in base $ 2 $ of the number of permutations satisfying the constraints described in the statement. Your answer is considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Formally, let your answer be $ x $ and let the correct answer be $ y $ . Your answer is accepted if and only if $ \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

说明

In the first sample, there is only one valid permutation, that is $ [2, 1] $ . Since $ \log_2(1)=0 $ , the correct output is $ 0 $ . In the second sample, there are $ 2 $ valid permutations, that are $ [3, 1, 2] $ and $ [2, 1, 3] $ . Since $ \log_2(2)=1 $ , the correct output is $ 1 $ . In the third sample, there are $ 4 $ valid permutations, that are $ [1, 5, 4, 3, 2] $ , $ [2, 5, 4, 3, 1] $ , $ [3, 5, 4, 2, 1] $ , $ [4, 5, 3, 2, 1] $ . Since $ \log_2(4)=2 $ , the correct output is $ 2 $ . In the fourth sample, there are $ 909 $ valid permutations. Notice that $ \log_2(909)=9.828136484194\ldots $

**计算排列数**

**题目描述：**
给定一个长度为 $ n-1 $ 的字符串 $ s $，其字符要么是 $ \texttt{<} $ 要么是 $ \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} $，如果 $ 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 $。

在第二个样例中，有两个有效的排列，即 $ [3, 1, 2] $ 和 $ [2, 1, 3] $。因为 $ \log_2(2)=1 $，正确的输出是 $ 1 $。

在第三个样例中，有四个有效的排列，即 $ [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 $**计算排列数** **题目描述：** 给定一个长度为 $ n-1 $ 的字符串 $ s $，其字符要么是 $ \texttt{<} $ 要么是 $ \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} $，如果 $ 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 $。 在第二个样例中，有两个有效的排列，即 $ [3, 1, 2] $ 和 $ [2, 1, 3] $。因为 $ \log_2(2)=1 $，正确的输出是 $ 1 $。 在第三个样例中，有四个有效的排列，即 $ [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 $