menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个带权糖果和 $n$ 个带权药片,求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。

解题报告

emm……我刚开始想的是求出 $\ge K$ 的方案数然后容斥来着,很不可做……实际上设 $A$ 为糖果大于药片,$B$ 为药片大于糖果,由于 $A+B=n,A=B+K$ 所以 $A={n+K\over2},B={n-K\over 2}$ 是已知的啊QAQ。

那么就不用管 $B$ 了,我们只要求出糖果大于药片的对数 $\ge A$ 的方案数就行了,这个可以通过先强制选出 $A$ 对糖果大于药片然后剩下的乱配对来求出。

考虑DP:$f_{i,j}$ 表示前 $i$ 个糖果匹配(糖果权值大于药片权值)了 $j$ 个的方案数,发现这样是假的,因为无法确定药片被匹配了的状态……不难想到糖果和药片都排序一下,这样大的糖果选的区间就包括了小的糖果选的区间,也就是说在 $f_{i,j}$ 状态时 $i$ 能匹配的已经用掉了 $j$ 个,令 $num_i$ 表示 $i$ 能匹配的数量,得到转移方程:

$$ f_{i,j}=f_{i,j-1}+(num_i-j+1)f_{i-1,j-1} $$

然后运用广义容斥(证明可以看这篇,应该是差不多的)将 $\ge A$ 转化为 $=A$ ,答案就是:

$$ \sum_{i=A}^{n}(-1)^{i-A}{i\choose A}f_{n,i}(n-i)! $$

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2000,MOD=1e9+9;

int n,K,a[maxn+5],b[maxn+5],num[maxn+5],f[maxn+5][maxn+5],fac[maxn+5],INV[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);if (n-K&1) return puts("0"),0;K=n+K>>1;Make(n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);sort(b+1,b+1+n);
    for (int i=1,j=1;i<=n;num[i++]=j-1) while (j<=n&&a[i]>b[j]) j++;
    for (int i=f[0][0]=1;i<=n;i++)
        for (int j=0;j<=i;j++)
            {f[i][j]=f[i-1][j];if (j&&num[i]>=j) AMOD(f[i][j],(LL)f[i-1][j-1]*(num[i]-j+1)%MOD);}
    for (int i=1;i<=n;i++) f[n][i]=(LL)f[n][i]*fac[n-i]%MOD;
    for (int i=K;i<=n;i++) {int now=i-K&1?MOD-1:1;now=(LL)now*C(i,K)%MOD*f[n][i]%MOD;AMOD(ans,now);}
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up