正题

题目链接:https://www.luogu.com.cn/problem/P4859

---

题目大意

两个长度为$n$的序列$a,b$两两匹配，求$a_i>b_i$的组数比$a_i<b_i$的组数多$k$的方案数。
保证输入数字两两不同

---

解题思路

其实就是求恰好有$\frac{n+k}{2}$种$a_i>b_i$的匹配方案。

先设$f_{i,j}$表示到$a$的第$i$个，已经选择了$j$组的方案。转移起来比较麻烦，我们不知道$b$中选了哪些。

把$a$和$b$排序后，设$l_i$表示一个最大的数字使得$a_i>b_{l_i}$，然后就可以$dp$了
$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (l_i-j+1)$$

之后发现我们很难固定其他配对的大小，可以考虑容斥，设$g_i$表示至少有$i$对满足$a_i>b_i$的方案，那么有$g_i=f_i\times (n-i)!$。
然后就可以直接容斥了，因为$g_i$中有$\left(\genfrac{}{}{0ex}{}{i}{k}\right)$中方案选出$k$个配对满足，所以容斥系数就是$(-1{)}^{i-k}(\genfrac{}{}{0ex}{}{i}{k})$
答案就是
$$\sum _{i=k}^n(-1{)}^{i-k}(\genfrac{}{}{0ex}{}{i}{k})g_i$$
时间复杂度$O(n^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2100,P=1e9+9; ll n,k,C[N][N],a[N],b[N],f[N][N],g[N],l[N],ans; signed main() {scanf("%lld%lld",&n,&k);if((n+k)&1)return puts("0")&0;k=(n+k)/2;C[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=0;j<=i;j++)C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);sort(a+1,a+1+n);sort(b+1,b+1+n);for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++)if(b[j]<a[i])l[i]=j;else break;f[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=0;j<=n;j++)f[i][j]=(f[i-1][j]+(j?f[i-1][j-1]*max(l[i]-j+1,0ll)%P:0))%P;for(ll i=n,s=1;i>=0;i--,s=s*(n-i)%P)g[i]=f[n][i]*s%P;for(ll i=k;i<=n;i++){ll tmp=g[i]*C[i][k]%P;(ans+=((i-k)&1)?P-tmp:tmp)%=P;}printf("%lld\n",ans);return 0; } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的P4859-已经没有什么好害怕的了【容斥,dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。