write by 小超手123
题意：
现在有四种物品，分别有 \(n_{1},n_{2},n_{3},n_{4}\) 个，有多少种排列物品的方案使得任意两个相邻物品的种类不同。
\(n_{1},n_{2} \le 200, \ \ n_{3},n_{4} \le 50000\)。
分析：
可以考虑先把物品 \(A,B\) 排列好，再把物品 \(C,D\) 插入进去。
需要注意的是 \(ABB\) 中 \(BB\) 中间必须填入 \(C,D\)。
记 \(f_{i,j,k,0/1}\) 表示用了 \(i\) 个物品 \(A\)，\(j\) 个物品 \(B\)，其中相邻的且相等有 \(k\) 对，当前最后一个选的物品 \(A/B\)。
step 1 : 分配哪些空位要填入 \(C,D\)
因此有 \(n_{1}+n_{2}+1\) 个空位，总共需用 \(C,D\) 填入 \(j\) 个空位，有 \(i\) 个空位已经强制要求必须填。\(i,j\) 均需要枚举。
那么方案数为：
\[(f_{n_{1},n_{2},i,1}+ f_{n_{1},n_{2},i,1}) \times \binom{n_{1}+n_{2}+1-i}{j-i} \]step 2 : 把 \(C,D\) 填入空位
可以发现中间空位填的 \(C,D\) 只有三种情况：
- 类型一：形如 \(CDCDC\)。相当于先放一个 \(C\) 进去，然后放若干个 \([DC]\)。即 \(C\) 的个数比 \(D\) 的个数多 \(1\)。记这样的有 \(X\) 种。
- 类型二：形如 \(DCDCD\)。相当于先放一个 \(D\) 进去，然后放若干个 \([CD]\)。即 \(D\) 的个数比 \(C\) 的个数多 \(1\)。记这样的有 \(Y\) 种。
- 类型三：形如 \(DCDC\) 或 \(CDCD\)。相当于直接放若干个 \([CD]\) 或 \([DC]\)。即 \(D\) 的个数与 \(C\) 的个数相等。记这样的有 \(Z\) 种。
不难发现 \(n_{1}-n_{2}=X-Y,Z=j-X-Y\)。因此只需要再枚举 \(X\) 即可。
所以可以给每个要填空位分配一种类型：\(\binom{j}{X} \times \binom{j-X}{Y}\)。
即上文所述 \([CD],[DC]\) 的总个数为 \(num\)。显然 \(num = \frac{n_{3}+n_{4}-X-Y}{2}\)。
将这 \(num\) 个\([CD],[DC]\) 放进 \(j\) 个空位里。需要注意的是对于类型三的空位，至少要放一个 \([CD]\) 或 \([DC]\)。
把 \(num\) 减掉 \(Z\)，然后插板即可。因此有 \(\binom{num-Z+j-1}{j-1}\) 种情况。
由于类型三有两种小情况，因此还要乘上 \(2^{Z}\)。
乘法原理，需要枚举 \(i,j,X\)。
最后答案就是：
\[(f_{n_{1},n_{2},i,1}+ f_{n_{1},n_{2},i,1}) \times \binom{n_{1}+n_{2}+1-i}{j-i} \times \binom{j}{X} \times \binom{j-X}{Y} \times \binom{num-Z+j-1}{j-1} \times 2^{Z} \]时间复杂度 \(O((n_{1}+n_{2})^3)\)。
标签：空位,数数,题解,个数,times,num,binom,CD From： https://www.cnblogs.com/cqyc-sol/p/18175639