将 \(a\) 和 \(b\) 两个数组都排序。
考虑恰好 \(k\) 个 \(a_i>b_i\) 的 \(i\) 并不好满足，那么计算至少 \(k\) 个满足 \(a_i>b_i\) 的 \(i\) 的方案数，“至少”的实现方法是钦定 \(k\) 个 \(a_i>b_i\) ，其余的都不确定。再使用二项式反演反演回去。
设 \(f_{i,j}\) 表示将 \(a_1\sim a_i\) 排序后一一与 \(b\) 中若干个数配对，钦定了 \(j\) 个 \(k\) 满足 \(a_k>b_k\) 的方案数（只考虑钦定的数的方案数，也就是说如果第 \(i\) 位没有 \(a_i>b_i\) 的时候，不需要乘上系数转移）。转移很简单：\(f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\cdot (l_i-j+1)\) 。边界是 \(f_{0,0}=1\) 。这样 \(f_{1,j}=f_{0,j}+f_{0,j-1}\cdot (l_i-j+1)\) 。
设 \(g_i\) 表示恰好 \(i\) 个 \(j\) 满足 \(a_j>b_j\) ，那么 \(f_{n,i}\cdot (n-i)!=\sum_{j=i}^n g_j\binom{j}{i}\) ，所以\(g_k=\sum_{i=k}^n f_{n,i}\cdot (n-i)!\cdot \binom{i}{k}(-1)^{i-k}\) .
原文：https://www.cnblogs.com/YouthRhythms/p/13693644.html