题意
现在有四种物品，分别有 \(n1, n2, n3, n4\) 个，有多少种排列物品的方案使得任意两个相邻物品的种类不同。
\(0 \le n1, n2 \le 500, 0 \le n3, n4 \le 5 \times 10 ^ 4\)
Sol
注意到 \(n1\)，\(n2\) 特别小。
设四个物品分别为 \(C, D, A, B\)。
考虑先插入 \(C, D\)，再考虑 \(A, B\) 插入的贡献。
设 \(f_{i, j, k, 0/1}\) 表示已经放了 \(i\) 个 \(C\) 物品，放了 \(j\) 个 \(D\) 物品，有 \(k\) 个相邻物品不合法，最后放了 \(0/1\)。
转移是简单的。
于是问题变成了，有 \(n1 + n2 + 1\) 个空隙，选 \(i\) 个空隙，其中我们钦定 \(j\) 个空隙必选，求 \(A, B\) 物品在每一段中合法的方案数。
显然，对于一个状态，\(C, D\) 物品的贡献为 \(f_{n1, n2, j, 0} + f_{n1, n2, j, 1}\)。
考虑怎么将 \(A, B\) 插入进去。
注意到显然每一段要么是形如 \(AB...A\)，或是 \(BA...B\)，以及 \(AB...B\)。
因为空隙数只有 \(n1 + n2 + 1\) 个，而每一段 \(A\) 与 \(B\) 的个数之差至多变化 \(1\)。
所以这个差值是不大的。
考虑由 \(k\) 枚举 \(BA...B\) 段的个数。
设 \(n = n3, m = n4\)，且 \(n \ge m\)。
显然，由 \(A\) 物品与 \(B\) 物品的差值可以算出 \(AB...\) 段的个数。
\[AB...A = n - m + k \]而对于 \(AB...B\) 段，可以通过剩余的空隙个数算出。
\[AB...B = i - n + m - 2k \]对于 \(A, B\) 没有填完的部分，则放在一起，当成 \(AB\) 填。
显然，对于 \(i\) 个位置都可以随便填，球同盒不同可空，插板即可。
答案就是：
\[\dbinom{n - i - 1}{k - 1}\dbinom{i - j}{n1 + n2 + 1 - j} \dbinom{k}{i} \dbinom{n - m + k}{i - k} g_i \times 2 ^ {i - n + m - 2k} \] 标签：2024054,count,AB,dbinom,...,省选,物品,n1,n2 From： https://www.cnblogs.com/cxqghzj/p/18178508