[Fortuna OJ]Mar 8th – Group A 解题报告

春季集训的最后一天了,果然比赛也崩了。

A – 涂色游戏

这道题怎么这么神仙啊。

我们先来考虑一行内的方案数。我们可以设出状态:\(f[i][j]\)代表前\(i\)个元素中有\(j\)种颜色,式子很好推:

\[ f[i][j] = f[i-1][j-1]*(p-(j-1))+f[i-1][j]*j \]

因为列数是固定的,所以我们只要保留当\(i=m\)的值即可,所以我们设\(g[i]=f[m][i]\),也就是单行有\(i\)种颜色的方案。之后我们考虑设计一个状态来求我们的答案:我们可以固定一行,然后讨论两行放在一起的情况。所以,\(dp[i][k]\)的意义是前\(i\)行的方案,其中最后一行包括了\(k\)种颜色。

\[ dp[i][k] = dp[i-1][j]+\frac{g[k]}{{ p \choose k }}*\sum_{ x = max\{ j,k,q \} }^{ min\{ p,j+k \} } { { j \choose j+k-x }*{ p-j \choose x-j } } \]

我知道这个式子很复杂,我们来解释一下。首先,状态\(dp[i][k]\)代表到了第\(i\)行,第\(i\)行有\(k\)种颜色,枚举上一行有\(j\)种颜色,所以从\(dp[i-1][j]\)转移过来。因为我们这里单独枚举颜色类型对答案的贡献,所以我们要消去\(g[i]\)中答案种类对\(g[i]\)的影响,避免算重。之后再枚举两行一共有\(x\)种颜色,因为\(j\)和\(k\)可能会有重复,所以我们需要单独枚举,这个\(x\)的上下界为:\( [max\{ j,k,q \},min\{ p, j+k \}] \)。之后就是喜闻乐见的两部分的单独枚举:\( { j \choose j+k-x } \)代表枚举两行共有的部分,\( { p-j \choose x-j } \)则是代表两行不共有的部分。所以,这样就可以把答案统计出来了。

然后这道题的\(f[i]\)可以用矩阵快速幂来搞,复杂度进一步降低。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注