CF840C On the Bench dp 题解

link
首先看到这个乘起来不为平方，想到消去平方因子。
题意就转化成了：求排列数量使 \(\forall a_{p_i}\neq a_{p_{i-1}}\)。
我们先将 \(a\) 序列排序，考虑 插入dp。令 \(dp_{i,j,k}\) 为现在排了 \(i\) 个数，有 \(j\) 对数相邻且相等，有 \(k\) 对数相邻且相等于 \(a_i\)。令前 \(i-1\) 个数中有 \(s\) 个数与他相同
当 \(a_i=a_{i-1}\) 时有四种情况。

1. 当前插入的数插入到的位置左右都与他相等。\(dp_{i,j,k}=dp_{i-1,j-1,k-1}\times (k-1)\)。
2. 当前插入的数插入到的位置左右有且仅有一个与他相等。\(dp_{i,j,k}=dp_{i-1,j-1,k-1}\times (2s-2(k-1))\)。
3. 当前插入的数插入到的位置原本左右相同，但它与左右不同。\(dp_{i,j,k}=dp_{i-1,j+1,k}\times (j-k)\)。
4. 当前插入的数插入到的位置只是一个普通的位置。\(dp_{i,j,k}=dp_{i-1,j,k}\times (i-k-(2s-2k)-(j-k))\)。

值得注意的是，这里有些地方不是用 \(k\) 转移，而是用 \(k-1\) 转移，因为 \(k\) 只是现在的状态，因为我们从过去转移来，所以应该用过去的状态。
当 \(a_i\neq a_{i-1}\) 。要先做 \(dp_{i-1,j,0}=\sum_{t=0}^j dp_{i-1,j-t,t}\)，再进行上述转移。毕竟是换了数字了。
然后答案即为 \(dp_{n,0,0}\)。注意这里数组能滚就滚吧。。。
这样的一种 dp 方式比较奇妙。（