【BZOJ3622】已经没有什么好害怕的了

题目大意

对于两个数列(a,b)，求有多少种排列(p,q)满足(a_{p_i}>b_{q_i})的个数恰好为(k)

题目分析

由“恰好”引发思考。

考虑容斥。

设询问函数(q(i))表示钦定(i)个(a>b)的关系的方案数。

再设贡献函数(g(i))表示有i个(a>b)关系的方案对答案的贡献。

再设容斥系数(f(i))，使得最终答案为(sum_{i=k}^nq(i)* f(i))

首先考虑如何快速求出询问函数(q(i))。首先将两个数列分别排序。设(dp[i][j])表示(a)数列前(i)个数的匹配关系处理后，钦定了(j)对关系的方案数。设(pos)表示(b_{pos}<a_i)的(pos)的最大值。显然有转移方程：

(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(pos-j+1))

那么(q(i)=dp[n][i]* (n-i)!)就能快速求出了。

再考虑求出容斥系数。

根据套路，我们可以(O(n^2))递推这玩意儿。

根据容斥原理，(g(x)=sum_{i=k}^xdbinom{x}{i}f(i))。

当(x=k)时，(g(x)=1)，那么显然(f(x)=1)

当(x>k)时，(g(x)=0)，则有：

(sum_{i=k}^xdbinom{x}{i}f(i)=0)

(sum_{i=k}^{x-1}dbinom{x}{i}f(i)+f(x)=0)

(f(x)=-sum_{i=k}^{x-1}dbinom{x}{i}f(i))

这样我们就能递推求出容斥系数了。时间复杂度(O(n^2))。

update：还有二项式反演的方法。

设(f(i))表示关系恰好有(i)个的方案数。

我们显然有：(q(x)=sumlimits_{i=x}^{n}dbinom{i}{x}f(i))

二项式反演后得到：(f(x)=sumlimits_{i=x}^{n}(-1)^{i-x}dbinom{i}{x}q(i))

就完了。