zcmimi's blog

arrow_back组合数学共1篇文章

avatar
zc
2020-02-16 18:54:00
查看原题

点击跳转

f[i,j]表示用完了前i种油漆,有j对相邻且同色的木块

考虑怎么转移:

要将第i种颜色的木块分两种情况插入:

  1. 设其中a个插到之前弄好的木块中间(无序)

  2. 设另外b个插在同色木块中间

其中有a-b组满足插空放且不相邻

f[i,j]=\sum f[i-1,j-(c_i-a-b)]\times {c_i-1 \choose a-1} \times {j \choose b} \times{S_{i-1}+1-j \choose a-b}

{c_i-1 \choose a-1}表示a个的方案数

{j \choose b}表示b个的方案数

{S_{i-1}+1-j \choose a-b}表示a-b个插进去的方案

1/1
Search
search