BZOJ 3622 已经没有什么好怕的了

扯淡

看到题目想到二项式反演

然后忘了给求阶乘的时候取模，调了一晚上

真令人窒息

思路

二项式反演

首先二项式反演还有另一种形式（不会证）

设\(G_i\)为有至少i个的方案数量，\(F_i\)为恰好有i个的方案数量

则有以下形式：

\[G_k=\Sigma_{i=k}^{n}C_i^kF_i \Rightarrow F_k=\Sigma_{i=k}^n(-1)^{i-k}C_i^kG_i
\]

所以套入本题

设\(F_i\)为恰好i对糖果比药片能量多的方案数，\(G_i\)为至少i对糖果比药片能量多的方案数

则可以对\(G_i\)dp求解

\(dp_{i,j}\)表示前i个，j对糖果比药片能量多的方案数，\(L_i\)是药片和糖果能量均从小到大排序后，最后一个能量小于第i个糖果的药片的标号，则\(G_i=dp_{n,i}\times(n-i)!\)，原因显然，j对之后剩下的随便排列即可，所以乘上阶乘

dp方程是

\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}*(L_i-j+1)
\]

然后二项式反演即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#define int long long

using namespace std;

int a[3000],b[3000],dp[3000][3000],jc[3000],g[3000],inv[3000],n,k,t;

const int MOD = 1000000009;

int pow(int a,int b){

    int ans=1;

    while(b){

        if(b&1)

            ans=(1LL*a*ans)%MOD;

        a=(1LL*a*a)%MOD;

        b>>=1;

    }

    return ans%MOD;

}

int C(int n,int m){

    return 1LL*jc[n]*inv[m]%MOD*inv[n-m]%MOD;

}

signed main(){

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

    if((n+k)%2){

        printf("0\n");

        return 0;

    }

    t=(n+k)/2;

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

        scanf("%lld",&a[i]);

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

        scanf("%lld",&b[i]);

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

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

    int lastpos=0;

    dp[0][0]=1;

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

        dp[i][0]=dp[i-1][0];

        for(int j=1;j<=i;j++){

            for(;b[lastpos]<a[i]&&lastpos<=n;lastpos++);

            lastpos--;

            dp[i][j]=(1LL*dp[i-1][j]+1LL*dp[i-1][j-1]*max(lastpos-j+1,0LL)%MOD)%MOD;

        }

    }

    jc[0]=1;

    inv[0]=1;

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

        jc[i]=1LL*jc[i-1]*i%MOD;

        inv[i]=pow(jc[i],MOD-2);

    }

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

        g[i]=1LL*dp[n][i]*jc[n-i]%MOD;

    int ans=0;

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

        ans=(ans+1LL*(((i-t)%2)?-1:1)*C(i,t)*g[i]%MOD)%MOD;

    printf("%lld\n",(ans%MOD+MOD)%MOD);

    return 0;

}

巴特西

BZOJ 3622 已经没有什么好怕的了

扯淡

思路

代码

最新文章

热门文章