열거

시간 제한5초메모리 제한512 MB

요약

각 a_k를 확률 p_k%로 독립적으로 선택할 때, 1부터 m까지의 정수 중 선택된 수 하나 이상으로 나누어지는 수의 개수에 대한 기댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 확률, 조합론, 수학, 비트 연산
정답자: 아직 제출이 없습니다

문제

$n$ 개의 정수 $a_1, a_2, \dots, a_n$ 과 $n$ 개의 정수 $p_1, p_2, \dots, p_n$ , 정수 $m$ 이 주어진다. 각 $k$ ( $1 \le k \le n$ )에 대해 $k$ 번째 정수 $a_k$ 를 $p_k\%$ 의 확률로 선택하는 조작을 하고, $0$ 개 이상 $n$ 개 이하의 정수를 고른다. $1$ 이상 $m$ 이하의 정수 중에서 고른 정수 중 적어도 하나로 나누어지는 것의 개수의 기댓값을 구하라.

입력

입력은 다음 형식으로 주어진다.

n m
a1 a2 … an
p1 p2 … pn

출력

문제의 답을 한 줄에 출력한다. 출력에는 절대 오차 또는 상대 오차로 $0.0000001(= 10^{-7})$ 을 초과하는 오차가 있어서는 안 된다.

제한

$1 \le n \le 20$
$1 \le m \le 10^{18}$
$1 \le a_k \le 10^{18}$ ( $1 \le k \le n$ )
$1 \le p_k \le 99$ ( $1 \le k \le n$ )

예제3

예제 1
입력
```
2 15
3 5
50 50
```
예상 출력
```
3.75
```
예제 2
입력
```
4 100
2 3 5 7
80 60 40 20
```
예상 출력
```
57.352
```
예제 3
입력
```
4 210
2 3 5 7
80 60 40 20
```
예상 출력
```
119.9136
```