[LGP4859,...] 一类奇怪的容斥套DP

漫山遍野都是fake的光影。

题目

[LGP4859] 已经没有什么好害怕的了

给定两个长度为n的数组a和b，将a中元素与b中元素配对，求满足ai>bj的配对(i,j)个数减去满足ai<bi的配对(i,j)个数恰好为k的方案数，保证ab中无重复元素。

[某年NOI欢乐赛] 决斗

给定两个长度为n的数组a和b，将a中元素与b中元素随机配对，求满足ai≥bj的配对(i,j)个数k次方的期望。

题解

对于前一个问题，我们转换为求满足ai>(≥)bj的配对(i,j)恰好为k=(n+k)/2的方案数。这样就能与第二个问题形式上保持一致。称这样配对的配对为“配对”（雾）。

其次将ab从小到大排序，然后依次为a数组配对，设f[i,j]表示前i个位置上确定了j个“配对”的方案数（跳过剩下的i-j对不为“配对”的配对的转移），w[i]表示满足bj≤ai的最大的j，有转移 f[i,j]=f[i-1,j]+f[i-1,j-1]*(w[i]-j+1)。后边那个系数其实是(w[i]-w[i-1])+(w[i-1]-(j-1))得来的。

如果你有兴趣尝试dp前i个位置上恰好有j个配对，会发现不为“配对”的情况根本dp不动。

考虑对f[n,i]统一确定剩下的(n-i)个配对，记g[i]=f[n,i]*(n-i)!。显然g[i]的统计是有重复的。具体的，设h[i]为恰好有i个“配对”的方案数，h[i]在g[j]中被统计C(i,j)次，其中i≥j。

即g[i]=Σ[j≥i] h[j]*C(j,i)，移项得h[i]=g[i] Σ[j>i] h[j]*C(j,i)，可以递推求解了。

后一个问题的后续操作已经不重要了你说是吧

参考实现

#include <bits/stdc++.h> #define ll long long using namespace std; const int N=2019; const int mod=1e9+9;int n,K,a[N],b[N],w[N],f[N][N],c[N][N];int main() {scanf("%d%d",&n,&K);for(int i=1; i<=n; ++i) scanf("%d",a+i);for(int i=1; i<=n; ++i) scanf("%d",b+i);if((n+K)&1) {puts("0");return 0;}K=(n+K)/2;sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1,j=0; i<=n; ++i) {while(j<n&&b[j+1]<=a[i]) ++j;w[i]=j;}for(int i=0; i<=n; ++i) {c[i][0]=1;for(int j=1; j<=i; ++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}f[0][0]=1;for(int i=1; i<=n; ++i) {f[i][0]=f[i-1][0];int J=min(i,w[i]);for(int j=1; j<=J; ++j) f[i][j]=(f[i-1][j]+(ll)f[i-1][j-1]*(w[i]-j+1)%mod)%mod;for(int j=J+1; j<=i; ++j)f[i][j]=f[i-1][j];}int fc=1;for(int i=n; i>=K; --i) {w[i]=(ll)f[n][i]*fc%mod;for(int j=i+1; j<=n; ++j) w[i]=(w[i]+mod-(ll)w[j]*c[j][i]%mod)%mod;fc=(ll)fc*(n-i+1)%mod;}printf("%d\n",w[K]);return 0; }

转载于:https://www.cnblogs.com/nosta/p/11174462.html

总结

以上是生活随笔为你收集整理的[LGP4859,...] 一类奇怪的容斥套DP的全部内容，希望文章能够帮你解决所遇到的问题。

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