Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2012-01-05

Codeforces100 E

18:50

n,m,p,{l_i} が与えられる.

n = |l|

m個の色 がある.

n個の列があって,各列は, l_i 個のマスからなる.

各マスに色を塗って,以下を満たす方法は何通りあるか. mod p で答えよ.

  • 各列で隣り合う色は異なる.
  • 隣接する列 で使われる色集合 は異なる

l_i <= 5000

sum {l_i} <= 1000万

m <= 100万

----------

a[i][j] = {1,2,...,i} を j 個の空でないサブセットにわけ,かつ 各サブセットに差が1であるものが入らない ようにする方法の数

とする.

a[1][1] = 1

a[i][j] = a[i-1][j-1] + a[i-1][j] * (j-1) *1


b[i][j] = i列目に j色 つかい, 前半 i 列 が問題の条件を満たす 方法の数

とする.

b[0][0] = 1

b[i][j] = sum_k { b[i-1][k] * ( ( choose(m,j) - [j = k] ) * a[l_i][j] * j ! }

= choose(m,j) * a[l_i][j] * j! * sum_k {b[i-1][k]} - a[l_i][j] * j ! * b[i-1][j]

choose(m,j) を mod p (素数とは限らない) で計算するのが難しそうだが,*2

j ! がかかっているので, m * (m-1) * ... * (m-j+1) を計算すれば良い.

O( max{l_i}^2 + sum {l_i} )



a[i][j] を, iマスを,j色で,同じ色が隣り合わないように塗る方法の数として 嵌っていた. ( 今のに j! をかけた値になる)

一般に,取り出せる組み合わせ係数があれば,取り出しておいて,かけるのを後回しにしたほうがいいのかも.

*1:iを,新しいサブセットとするか, i-1が入っている以外のところに入れる

*2:Petrはそういう感じのことをやっている? よくわかってない

 |