TDPC D - サイコロ

考え方

ABCでいうと、易しめのE問題級。

出た目の積が $D$ の倍数というのを、出た目の積と $D$ の最大公約数が $D$ そのものになると言い換える。
「今の積と $D$ の最大公約数がいくつになっている確率がいくつか」を DP テーブルに持てばよい。
サイコロを $1$ 回振るごとのテーブル更新は、配るDPの方が楽。
今の最大公約数が $i$ だったら、$i,2i,3i,4i,5i,6i$ それぞれと $D$ の最大公約数に $1/6$ ずつ配ればよい。
これで、サイコロの目の数 $6$ は定数とみなして、$O(ND)$ で解ける。
が、$D$ が $10^{18}$ まであるので、これではメモリも計算量も足りなくなる。

しかし、DPテーブルに意味がある値が入るのは、$D$ の約数のみである。
よって、テーブルを配列でもつのではなく map か何かで持てば高速化される。

素因数を $2,3,5$ しか持たない $D$ の約数の個数を $M$ とすると、計算量は $O(NM\log M)$。
これが最も多いのは $D=2^{19}\times 3^{14}\times 5^8=979552051200000000$ のときの $M=2700$。
よって、十分間に合う。

入力例1での動作

入力を受け取る。

n: 2
d: 6

mp[i] を、ここまでの出目の積と $d$ の最大公約数が $i$ になる確率とする。
最初は出目をまだ掛けていないので、積を $1$ として次の状態から始める。

$1$ 回目のサイコロを振る。
出目が $1,5$ なら最大公約数は $1$、$2,4$ なら $2$、$3$ なら $3$、$6$ なら $6$ になる。

さらに $2$ 回目のサイコロを振る。
$1$ 回目の各結果から同様に最大公約数へ配る DP をすると、次の状態になる。

最大公約数が $6$ であることと、出目の積が $6$ の倍数であることは同値である。
したがって、$\frac{15}{36}=0.416666\ldots$ が答え。

注意点

特になし。

別解

特になし。