読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Typical DP Contest D - サイコロ

AtCoder 動的計画法

tdpc.contest.atcoder.jp

解法

積の倍数判定の場合は、gcd(a0 a1 ... an-1,D)=D なら a0 a1 ... an-1 は D の倍数という判定法が使える。

これを使うと

  • dp[ 振ったサイコロの個数 ][ gcd(サイコロの目の積,D) ] := 確率

ができる。状態数は D の約数のうち素因数に 2,3,5 を持つものしか現れないので計算量はそんなに大きくならない。


ギリギリオーバーフローしない。

Typical DP Contest D - サイコロ

汎用的なテク。