bzoj 3622 已经没有什么好害怕的了——二项式反演

时间：2021-12-13 16:18:15

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3622

令 f[i] 表示钦定 i 对 a[ ]>b[ ] 的关系的方案数；g[i] 表示恰好 i 对 a[ ]>b[ ] 的关系的方案数。

那么 \(f[i]=\sum\limits_{j>=i}C_{j}^{i}*g[j] \) ，\(g[i]=\sum\limits_{j>=i}C_{j}^{i}f[j](-1)^{j-i} \)

考虑怎么求 f[ ] 。可以 DP 。

先把 a[ ] 和 b[ ] 都按从小到大的顺序排序，dp[i][j]表示前 i 个 a[ ] 匹配了 j 对 a[ ] > b[ ] 的关系的方案数。

排序的好处就是 a[ ] > b[ ] 的一段 b[ ] ，a[i] 的这一段能包含 a[i-1] 的这一段。所以转移就是 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(p0-(j-1))，其中p0是比 a[i] 小的 b[ ] 的个数。

然后别忘了 f[ i ] = dp[n][i]*(n-i)! ，阶乘表示其他配对可以随意。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int Mn(int a,int b){return a<b?a:b;}

const int N=,mod=1e9+;

int upt(int x){if(x>=mod)x-=mod;return x;}

int n,k,a[N],b[N],dp[N],c[N][N];

void init()

{

    for(int i=;i<=n;i++)c[i][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            c[i][j]=upt(c[i-][j]+c[i-][j-]);

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)scanf("%d",&b[i]);

    k+=n;if(k&){puts("");return ;}//

    k>>=;

    sort(a+,a+n+); sort(b+,b+n+);

    int p0=;dp[]=;

    for(int i=;i<=n;i++)

    {

        while(p0<n&&b[p0+]<a[i])p0++;

        for(int j=Mn(i,p0);j;j--)

      dp[j]=(dp[j]+(ll)dp[j-]*(p0-j+))%mod;

    }

    for(int i=n,lj=,j=;i;i--,j++,lj=(ll)lj*j%mod)

      dp[i]=(ll)dp[i]*lj%mod;

    int ans=; init();

    for(int i=k,j=;i<=n;i++,j=-j)

        ans=(ans+(ll)dp[i]*j*c[i][k])%mod;

    if(ans<)ans+=mod; printf("%d\n",ans);

    return ;

}

相关文章