Typical DP Contest D - サイコロ
解法
積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。
これを使うと
- dp[ 振ったサイコロの個数 ][ gcd(サイコロの目の積,D) ] := 確率
ができる。状態数は D の約数のうち素因数に 2,3,5 を持つものしか現れないので計算量はそんなに大きくならない。
ギリギリオーバーフローしない。
汎用的なテク。
積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。
これを使うと
ができる。状態数は D の約数のうち素因数に 2,3,5 を持つものしか現れないので計算量はそんなに大きくならない。
ギリギリオーバーフローしない。