問題概要

短い問題文なので概要も何もないですが、

N個のM色のブロックを同じ色が連続するところがK箇所以下になるように並べる並べ方はいくつですか、

という問題です。いわゆる数え上げ問題ですね。

解答までの道のり

まず動的計画法を書こうと思いました。左からIまでブロックを置いて連続する場所がJ箇所というのは何種類か、というのを記録した配列DP(I,J)をもってDP(N,K)まで計算します。そして、DP(N,0)からDP(N,K+1)まで足していけば回答が出そうです。しかしこの方法だとNxK回計算しないといけないので早々に諦めました。

そこで、方針を改めて、同じ色が連続する箇所が0箇所となるようにN個並べる方法から発展できないか、と考えました。同じ色が連続する箇所が0箇所となるようにN個並べる並べ方の個数は次の式で求められます。

$\displaystyle{ M\times (M-1) ^ {N-1} }$

では同じ色が連続する箇所が1箇所となるようにN個並べる並べ方の個数はどうやって求められるでしょうか。同じ色が連続する箇所が1箇所ということは、同じ色が連続しないようにN-1個並べたあとどこか1箇所そこと同じ色のブロックを増やしてあげるというのと同じです。というわけでとりあえず同じ色が連続しないようにN-1個並べる方法を求めます。これは先ほどとほとんど同じような式で求められます。

$\displaystyle{ M\times (M-1) ^ {N-1-1} }$

N-1個のブロックのうちどのブロックの隣にそのブロックと同じ色のブロック1個を足すか、の数がかかります。 N-1個のブロックのうちどれか1つのブロックの隣にそのブロックと同じ色のブロック1個足す方法はN-1です。よって同じ色が連続する箇所が1箇所となるようにN個並べる並べ方の個数は

$\displaystyle{ M\times (M-1) ^ {N-1-1}\times(N-1) }$

で求められます。

さて、では同じ色が連続する箇所がk箇所となるようにN個並べる並べ方の個数はどうやって求められるでしょうか。1個の時と同様に同じ色が連続する箇所がk箇所ということは、同じ色が連続しないようにN-k個並べたあとすでにあるブロックのとなりにそのブロックと同じ色のブロックを合計でk個足してあげるというのと同じです。同じ色が連続しないようにN-k個並べる方法は

$\displaystyle{ M\times (M-1) ^ {N-k-1} }$

で求められます。同じ色が連続しないようにN-k個並べたあと、すでに並べられたブロックのとなりにそのブロックと同じ色のブロックを合計でk個足してあげる方法の数はN-k個のブロックのうち増やすブロックkを分け合うという考え方で求められます。この組み合わせの数はまあ落ち着いてやれば導き出せるんですけど、あんまりいろいろ考えたくないのでWEBを頼ると

mathtrain.jp

というのが出てくるのでそれを考えると

$\displaystyle{ _ {N-k} H _ {k} = _{N-1} C _ k }$

で求められます。

こうして同じ色が連続する箇所がk箇所となるようにN個並べる並べ方の個数は

$\displaystyle{ M\times (M-1) ^ {N-k-1} \times {} _{N-1} C _ k }$

で求められるとわかりました。

これで0箇所のとき、1箇所のとき、・・・、K箇所のときと計算していき足し合わせれば答えが出るはずです。

実装

modintを借りて行いました

program em
  use mod_modint
  implicit none
  integer::N,M,K
  type(modint),allocatable,dimension(:)::M_1,P
  type(modint)::ans
  integer::i
  read*,N,M,K
  allocate(P(0:N))
  P(0)=1
  do i=1,N
    P(i)=P(i-1)*i
  end do
  allocate(M_1(0:N))
  M_1(0)=1
  do i=1,N
    M_1(i)=M_1(i-1)*(M-1)
  end do
  ANS=0
  do i=0,K
    ANS=ANS+M*M_1(N-1-i)*Comb(N-1,i)
  end do
  print"(I0)",getnum(ANS)
  contains
function Comb(kk,jj)
  type(modint)::comb
  integer::kk,jj
  Comb=P(kk)/(P(kk-jj)*P(jj))
end function
end program em

おしまい。

しずくぶろぐ

競技ぷろぐらみんぐしたり、なんかしたりします

不定期解説記事企画 ABC167 E #雫ぷよ

問題概要

解答までの道のり

実装