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

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]\)可以用矩阵快速幂来搞，复杂度进一步降低。