回答編集履歴
3
繰り返し二乗法
answer
CHANGED
|
@@ -6,6 +6,7 @@
|
|
|
6
6
|
追記) 愚直に計算を行うのではなく、前処理で素因数分解を行うことで高速(マイクロ秒くらい)に解けることを確認しました。
|
|
7
7
|
まずは、エラトステネスの篩で素数列挙を行い, 通常の整数では素数で順番に割り算してどこまで割れるか試していき、階乗ではルジャンドルの定理を使って、素因数分解を行います。
|
|
8
8
|
指数の足し算を行ったあと、実際に掛け算を行って、有理数(powplus/powminus)を求めてやります。
|
|
9
|
+
(なお、掛け算時に累乗を計算する必要がありますが、これは繰り返し二乗法を使って高速化します。)
|
|
9
10
|
ここまでは整数同士の掛け算割り算なので誤差はありませんが、最後に割り算を行い小数に直します。
|
|
10
11
|
(試作のためpythonですが, 流れさえわかれば, javaでも組めると思います。javaでも書こうと思いましたが、pythonで力尽きました)
|
|
11
12
|
|
2
pythonによるテスト
answer
CHANGED
|
@@ -1,4 +1,116 @@
|
|
|
1
1
|
>上記パスカルの三角形を利用したコードで1000000007で割った余りを利用して、二項分布を使い「確率pをn回試行した時にk回当たる確率」を求めるにはどうすれば良いでしょうか
|
|
2
2
|
競技プログラミングで組み合わせを求めるときはオーバーフローを防ぐため余りを使うことはやりますが、確率で余りをつかうことはできないと思います。
|
|
3
3
|
|
|
4
|
-
二項分布にはほかの分布で近似されることが知られています。正規分布(np>5 np(1-p)>5のとき) あるいはポアソン分布(nが大きくpが十分に小さい場合)で近似できるため、こころへんの性質をつかうといいのではないでしょうか。
|
|
4
|
+
二項分布にはほかの分布で近似されることが知られています。正規分布(np>5 np(1-p)>5のとき) あるいはポアソン分布(nが大きくpが十分に小さい場合)で近似できるため、こころへんの性質をつかうといいのではないでしょうか。
|
|
5
|
+
|
|
6
|
+
追記) 愚直に計算を行うのではなく、前処理で素因数分解を行うことで高速(マイクロ秒くらい)に解けることを確認しました。
|
|
7
|
+
まずは、エラトステネスの篩で素数列挙を行い, 通常の整数では素数で順番に割り算してどこまで割れるか試していき、階乗ではルジャンドルの定理を使って、素因数分解を行います。
|
|
8
|
+
指数の足し算を行ったあと、実際に掛け算を行って、有理数(powplus/powminus)を求めてやります。
|
|
9
|
+
ここまでは整数同士の掛け算割り算なので誤差はありませんが、最後に割り算を行い小数に直します。
|
|
10
|
+
(試作のためpythonですが, 流れさえわかれば, javaでも組めると思います。javaでも書こうと思いましたが、pythonで力尽きました)
|
|
11
|
+
|
|
12
|
+
```python
|
|
13
|
+
from decimal import *
|
|
14
|
+
# 素数列挙(エラトステネスの篩)
|
|
15
|
+
def eratosthenes(n):
|
|
16
|
+
primeNumbers = []
|
|
17
|
+
isprime = [True]*(n+1)
|
|
18
|
+
for i in range(2, n+1):
|
|
19
|
+
if(isprime[i]):
|
|
20
|
+
primeNumbers.append(i)
|
|
21
|
+
temp = i
|
|
22
|
+
while(temp <= n):
|
|
23
|
+
isprime[temp] = False
|
|
24
|
+
temp += i
|
|
25
|
+
return primeNumbers
|
|
26
|
+
|
|
27
|
+
# n!を素因数分解(ルジャンドルの定理)
|
|
28
|
+
def primeFactorizeKaijo(n, primeNumbers):
|
|
29
|
+
assert(n <= max_int)
|
|
30
|
+
res = {}
|
|
31
|
+
for i in primeNumbers:
|
|
32
|
+
if(i > n):
|
|
33
|
+
break
|
|
34
|
+
temp = i
|
|
35
|
+
restemp = 0
|
|
36
|
+
while(temp <= n):
|
|
37
|
+
restemp += int(n/temp)
|
|
38
|
+
temp *= i
|
|
39
|
+
res[i] = restemp
|
|
40
|
+
return res
|
|
41
|
+
|
|
42
|
+
# nを素因数分解する
|
|
43
|
+
def primeFactorize(n, primeNumbers):
|
|
44
|
+
assert(n <= max_int)
|
|
45
|
+
res = {}
|
|
46
|
+
temp = n
|
|
47
|
+
for i in primeNumbers:
|
|
48
|
+
if(i > temp):
|
|
49
|
+
break
|
|
50
|
+
while(temp % i == 0):
|
|
51
|
+
if(i in res):
|
|
52
|
+
res[i] += 1
|
|
53
|
+
else:
|
|
54
|
+
res[i] = 1
|
|
55
|
+
temp /= i
|
|
56
|
+
return res
|
|
57
|
+
def calculatePowMul(ans, fact, power):
|
|
58
|
+
for k, v in fact.items():
|
|
59
|
+
ans[k] += v*power
|
|
60
|
+
|
|
61
|
+
# nCk * p^k * q^{n-k}
|
|
62
|
+
n = 10000
|
|
63
|
+
k = 5000
|
|
64
|
+
|
|
65
|
+
# p = [pの分子, pの分母]
|
|
66
|
+
p = [1, 65535]
|
|
67
|
+
max_int = max([n, k, p[0], p[1]])
|
|
68
|
+
|
|
69
|
+
# 素因数分解
|
|
70
|
+
primeNumbers = eratosthenes(max_int)
|
|
71
|
+
pbunbo_fact = primeFactorize(p[1], primeNumbers)
|
|
72
|
+
pbunshi_fact = primeFactorize(p[0], primeNumbers)
|
|
73
|
+
qbunshi_fact = primeFactorize(p[1]-p[0], primeNumbers)
|
|
74
|
+
nkaijo_fact = primeFactorizeKaijo(n, primeNumbers)
|
|
75
|
+
kkaijo_fact = primeFactorizeKaijo(k, primeNumbers)
|
|
76
|
+
nmkkaijo_fact = primeFactorizeKaijo(n-k, primeNumbers)
|
|
77
|
+
|
|
78
|
+
# 指数同士の足し算をおこない、掛け算する
|
|
79
|
+
ans = [0]*(max_int+1)
|
|
80
|
+
calculatePowMul(ans, pbunbo_fact, -n)
|
|
81
|
+
calculatePowMul(ans, pbunshi_fact, k)
|
|
82
|
+
calculatePowMul(ans, qbunshi_fact, n-k)
|
|
83
|
+
calculatePowMul(ans, nkaijo_fact, 1)
|
|
84
|
+
calculatePowMul(ans, kkaijo_fact, -1)
|
|
85
|
+
calculatePowMul(ans, nmkkaijo_fact, -1)
|
|
86
|
+
|
|
87
|
+
# 指数の正負で分ける(0は入れない)
|
|
88
|
+
plus = {}
|
|
89
|
+
minus = {}
|
|
90
|
+
for i in primeNumbers:
|
|
91
|
+
if(ans[i] > 0):
|
|
92
|
+
plus[i] = ans[i]
|
|
93
|
+
if(ans[i] < 0):
|
|
94
|
+
minus[i] = abs(ans[i])
|
|
95
|
+
|
|
96
|
+
# 実際に掛け算を行う(
|
|
97
|
+
powplus = 1
|
|
98
|
+
for i in plus:
|
|
99
|
+
powplus *= pow(i, plus[i])
|
|
100
|
+
powminus = 1
|
|
101
|
+
for i in minus:
|
|
102
|
+
powminus *= pow(i, minus[i])
|
|
103
|
+
|
|
104
|
+
# 有効桁数を50桁とする
|
|
105
|
+
getcontext().prec = 50
|
|
106
|
+
|
|
107
|
+
# 実際に割って小数にする
|
|
108
|
+
print(Decimal(powplus)/Decimal(powminus))
|
|
109
|
+
```
|
|
110
|
+
|
|
111
|
+
```text
|
|
112
|
+
CPU times: user 3 µs, sys: 0 ns, total: 3 µs
|
|
113
|
+
Wall time: 5.25 µs
|
|
114
|
+
6.3420873578683450119531499686198773734249989811395E-21075
|
|
115
|
+
```
|
|
116
|
+
ほぼ無視できるような確率ですね。
|
1
修正
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
1
|
>上記パスカルの三角形を利用したコードで1000000007で割った余りを利用して、二項分布を使い「確率pをn回試行した時にk回当たる確率」を求めるにはどうすれば良いでしょうか
|
|
2
2
|
競技プログラミングで組み合わせを求めるときはオーバーフローを防ぐため余りを使うことはやりますが、確率で余りをつかうことはできないと思います。
|
|
3
3
|
|
|
4
|
-
|
|
4
|
+
二項分布にはほかの分布で近似されることが知られています。正規分布(np>5 np(1-p)>5のとき) あるいはポアソン分布(nが大きくpが十分に小さい場合)で近似できるため、こころへんの性質をつかうといいのではないでしょうか。
|