题意：给定两个长度 \(n\) 的互不相同的序列 \(a,b\)。要求将它们两两匹配。求有多少种匹配方案恰好有 \((n+k)/2\) 对 \(a_i>b_j\)。\(n\le 2000\)。如果 \((n+k)\bmod 2=1\) 输出 \(0\)。
先将 \(a,b\) 从小到大排序。\(dp_{i,j}\) 表示让 \(a_{1\sim i}\) 匹配 \(b_{1\sim n}\)，至少有 \(j\) 对 \(a_x>b_y\) 的方案数。
记 \(r_i\) 表示：\(b_{1\sim r_i}<a_i\)，\(b_{r_i+1}>a_i\)。
则 \(dp[i][0]=dp[i-1][0],dp[i][j]=dp[i-1][j]+(r_i-j+1)dp[i-1][j-1]\)。可以 \(O(n^2)\) DP。
则至少有 \(i\) 对 \(a_x>b_y\) 的方案数是 \(f_i=dp_{n,i}\times (n-i)!\)。
然后怎么求恰好？
二项式反演：至少转恰好。
\[g(n)=\sum_{i=1}^n C_n^i\cdot f(i)\iff f(n)\sum_{i=1}^n (-1)^{n-i} C_n^i \cdot g(i) \]则 \(ans=\displaystyle\sum_{i=k}^n(-1)^{i-k}C_i^k\cdot f_i\)。
标签：匹配,P4859,cdot,sum,害怕,dp,什么,sim From： https://www.cnblogs.com/FLY-lai/p/18109296