很好的一道容斥题
我们如果想让\(a_i > b_i\)的个数比\(a_i < b_i\)的对数多\(K\)，这个限制是比较困难的。因为我们要同时考虑两种情况
但我们可以把原问题的限定设为\(a_i > b_i\)的对数为\(\frac{n+K}{2}\)，做法就容易了很多。如果\(n+K\)是奇数，直接输出\(0\)即可
因此原问题变为了找一种配对方案，使得\(a_i > b_i\)的对数恰好为\(k\)
这个恰好的限制又过于严格，很明显不是我们想要的，因此我们考虑容斥原理。具体的，先求出\(f_i\)表示满足条件的配对对数\(\geq i\)的方案数，\(g_i\)表示满足条件的配对对数\(= i\)的方案数
容易得到以下规律：
\[f_i = \sum_{j=i}^{n}{\binom{j}{i} g_j} \]其中\(\binom{j}{i}\)我们从恰好对数\(= j\)的配对对数中选出\(i\)对来，剩下的当成随机匹配
根据二项式反演可得
\[g_i = \sum_{j=i}^{n}{(-1)^{j-i}\binom{j}{i} f_j} \]最终答案就是\(\large{g_{\frac{n+K}{2}}}\)，因此我们只需要求\(f_i\)的值即可，这是比较好求的
我们设\(dp_{i,j}\)表示前\(i\)个数，钦定了\(j\)个满足\(a_p > b_p\)的方案数
容易得到递推式：
\[dp_{i,j} = dp_{i-1,j} + (ls_i - j + 1) \times dp_{i-1,j-1} \]最后容易直到\(f_i = dp_{n,i} \times (n-i)!\)，其中\((n-i)!\)表示未被匹配的随便分配的方案数
最终复杂度\(O(n^2)\)
标签：方案,P4859,什么,害怕,对数,binom,配对,我们,dp From： https://www.cnblogs.com/fox-konata/p/17699914.html