ABC300 E問題 Dice Product 3

atcoder.jp

積が N になるための出た目の回数

サイコロを何回か振った結果、1,2,3,4,5,6 の目が出た回数がそれぞれ 回のとき、全部の積を素因数分解すると、

となります。これが N と一致するためには、まず N を

の形に素因数分解でき、かつ



が成り立てばよいです。N の素因数分解で、2,3,5 以外の素数が現れたら不可 (確率 0) です。

サイコロを振って出た目を掛けていってN になる確率を求める問題です。N を素因数分解して、2,3,5 以外の素数がある場合は、サイコロの目を掛けていっても N に一致することはありません。(確率 0)
素因数分解した結果を、 とします。

コード例 (Julia)

MOD_ = 998244353

fact    = Vector{Int}()
invfact = Vector{Int}()

function setup_fact(N)
  resize!(fact,N)
  resize!(invfact,N)

  fact[1] = 1
  invfact[1] = 1
  for i = 2:N
    fact[i] = (i * fact[i-1]) % MOD_    # N!
    invfact[i] = invmod(fact[i],MOD_)   # 1/N!
  end
end

function f5(d2,d3,d4,d5,d6)

  if d2 < 0 || d3 < 0 || d4 < 0 || d5 < 0 || d6 < 0
    return 0
  end

  sum = d2 + d3 + d4 + d5 + d6

  n = fact[sum]
  n %= MOD_
  n = d2 > 1 ? (n*invfact[d2])%MOD_ : n
  n = d3 > 1 ? (n*invfact[d3])%MOD_ : n
  n = d4 > 1 ? (n*invfact[d4])%MOD_ : n
  n = d5 > 1 ? (n*invfact[d5])%MOD_ : n
  n = d6 > 1 ? (n*invfact[d6])%MOD_ : n

  return n
end

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  # N を 2 で何回割り切れるか
  n2 = 0
  while mod(N,2) == 0
    n2 += 1
    N = div(N,2)
  end

  # N を 3 で何回割り切れるか
  n3 = 0
  while mod(N,3) == 0
    n3 += 1
    N = div(N,3)
  end

  # N を 5 で何回割り切れるか
  n5 = 0
  while mod(N,5) == 0
    n5 += 1
    N = div(N,5)
  end

  # 2,3,5 以外の素因数があれば、不可(確率 0)
  if N != 1
    println(0)
    return
  end

  # n!,  1/n! をあらかじめ計算しておく
  M = max( n2+n3+n5, 5 )
  setup_fact(M)

  ans = 0

  for d4 = 0:n2
    for d6 = 0:max(n2,n3)
      d2 = n2 - 2 * d4 - d6
      if d2 < 0
        continue
      end
      d3 = n3 - d6
      if d3 < 0
        continue
      end
      d5 = n5

      sum = d2 + d3 + d4 + d5 + d6

      # (1/5)^sum
      c = powermod(invmod(5,MOD_), sum, MOD_)

      # 組み合わせ数をかける
      c *= f5(d2,d3,d4,d5,d6)
      c %= MOD_

      ans += c
      ans %= MOD_

    end
  end

  println(ans)

end  # function solve

# main
solve()