ABC297 F問題 Minimum Bounding Box 2

atcoder.jp

期待値の求め方

マスの数は個で、ここから 個 の選び方は、 通りです。
選んだマスの位置を とすると、スコアは となります。

スコアが になる選び方が 通りあるとすると、スコアの期待値は

と計算されます。ここから を求めることを考えていきます。

場合の数の計算

縦 マス、横マスの固定範囲内で マスの選び方は 通りですが、これにはスコアが より小さな選び方も含んでいます。
そこで外側の4辺について、辺上に選んだマスがある場合(〇)とひとつも無い場合(×)で分類します。これによってマスの選び方を 種類に分類できます。

求めたいのは、①の場合の数です。

選び方全体

辺A のマスを選ばない選び方

辺C のマスを選ばない選び方

辺B のマスを選ばない選び方

辺D のマスを選ばない選び方

辺A,B のマスを選ばない選び方

辺B,C のマスを選ばない選び方

辺C,D のマスを選ばない選び方

辺D,A のマスを選ばない選び方

辺A,C のマスを選ばない選び方

辺B,D のマスを選ばない選び方

辺A,B,C のマスを選ばない選び方

辺A,D,C のマスを選ばない選び方

辺A,B,D のマスを選ばない選び方

辺C,B,D のマスを選ばない選び方

4辺すべてのマスを選ばない選び方

以上の16式から16個の変数を求めると、 と表示することにして

縦 マス、横マスの範囲の選び方は 通りあるため、結局、

となります。

コード例 (Julia)

const MOD_ = 998244353

const NMAX = 1_000_000

fact    = Vector{Int}(undef, NMAX)
invfact = Vector{Int}(undef, NMAX)

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

function Comb( N, M )
  if N < 0 || M < 0 || N - M < 0
    return 0
  end
  if M == 0 || N - M == 0
    return 1
  end

  ret = (invfact[M] * invfact[N-M])%MOD_
  ret *= fact[N]
  return ret % MOD_
end

function solve()


  # あらかじめ n!, 1/n! を計算
  setup_fact()

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

  H,W,K = readInts()

  F = zeros(Int, H, W)

  for h=1:H, w=1:W
    F[h,w] = Comb( h*w, K )
  end

  ans = 0

  for h=1:H, w=1:W
    maru1 = F[h,w]
    maru1 += (h>1) ? -2*F[h-1,w] : 0
    maru1 += (w>1) ? -2*F[h,w-1] : 0
    maru1 += (h>1&&w>1) ? 4*F[h-1,w-1] : 0
    maru1 += (w>2) ?   +F[h,w-2] : 0
    maru1 += (h>2) ?   +F[h-2,w] : 0
    maru1 += (h>1&&w>2) ? -2*F[h-1,w-2] : 0
    maru1 += (h>2&&w>1) ? -2*F[h-2,w-1] : 0
    maru1 += (h>2&&w>2) ?   +F[h-2,w-2] : 0
    maru1 %= MOD_
    if maru1 < 0
      maru1 += MOD_
    end
    coef = h * w * (H-h+1) * (W-w+1)
    coef %= MOD_
    ans += coef * maru1
    ans %= MOD_
    if ans < 0
      ans += MOD_
    end
  end

  ans *= invmod(F[H,W], MOD_)
  ans %= MOD_

  println(ans)

end  # function solve

# main
solve()