《来一道经典dp》
给若干个盒子，每个盒子里面有若干个 本质不同 的小球，你要从这些盒子中选取小球，问有多少种选取方案使得任意两个相邻的小球不来自于同一个盒子里面（注：全部小球都要选完）
设 \(f_{i,j}\) 为选了 \(i\) 个数有 \(j\) 个位置是不合法的（就是说相邻的小球相同的位置数）
设 \(a_x\) 表示 \(x\) 盒子中小球数量。
那么我们就有转移 \(f[i+k][j+d]=f[i][j]\times C_{a[x]}^k\times g[i][j][k][d]\)
\(g[i][j][k][d]\) 表示原本有 \(i\) 个数，\(j\) 个不合法的位置，加入 \(k\) 个数，增加 \(d\) 个不合法位置的方案数。
当然这个 \(d\) 可能是负数，因为可能把一些不合法位置给填掉，我们设填掉了 \(b\) 个不合法位置，由于我们要增加 \(d\) 个不合法位置，所以我们自己就得产生 \(b+d\) 个不合法的位置。
我们先考虑将 \(b\) 填掉，从 \(j\) 个不合法位置中选择 \(b\) 个填掉。 \(C_j^b\)
接着我们先保留 \(b+d\) 个数，用来构成不合法位置，我们先将剩下 \(k-b-(b+d)\) 个数先填掉，同时保证这些数不构成不合法格子数，剩下的空隙就是 \(i+1-b\) 。\(C_{i+1-b}^{k-2b-d}\)
然后这时候我们就有了 \(k-b-d\) 个位置是我们至少填了一个数的位置，然后我们还要填 \(b+d\) 个数，\(C_{b+d+(k-b-d-1)}^{b+d}=C_{k-1}^{(k-1)-(b+d)}\)。
然后由于小球本质不同所以要乘上 \(k!\)
最后式子
\(g_{i,j,k,d}=\sum\limits_b C_j^b\times C_{i+1-b}^{k-2b-d}\times C_{k-1}^{(k-1)-(b+d)}\times k!\)
然后我们 \(O(n^5)\) 预处理 \(g\) ，对于每个 \(f\) \(O(n^4)\) 求。