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

BZOJ

Luogu

分析

输入进来先sort一遍。

设$f[i][j]$表示前$i$对中,(糖果>药片)至少有$j$对的方案数。

转移比较简单,设$s$为所有满足糖果$i$>药片$s$的$s$中最大的$s$,则有$\large f[i][j]=f[i-1][j]+f[i-1][j-1]\times(s-j+1)$

最后用容斥原理统计答案。

然后交上去,发现你得到了Wrong Answer

原因在于,$n+k$为奇数时是没有解的。此时要特判,输出$0$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}
 
const int MAXN=2000+10;
const int MOD=1e9+9;
 
int a[MAXN],b[MAXN];
int fact[MAXN],inv[MAXN];
int f[MAXN][MAXN];
 
inline int FastPow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%MOD)
        if (b&1) ans=1ll*ans*a%MOD;
    return ans;
}
 
inline int C(int n,int m) {
    return 1ll*fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
 
inline void init(int n) {
    fact[0]=1;
    for (re int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%MOD;
    inv[n]=FastPow(fact[n],MOD-2);
    for (re int i=n-1;i>=0;--i) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
}
 
int main() {
    int n=read(),k=read();
    if ((n+k)&1) { puts("0"); return 0; } //特判
    init(n);
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) b[i]=read();
    sort(a+1,a+n+1); sort(b+1,b+n+1);
     
    f[0][0]=1;
    for (re int i=1,s=0;i<=n;++i) {
        while (s<n&&b[p+1]<a[i]) ++s;
        for (re int j=1;j<=i;++j) {
            f[i][j]=(f[i][j]+f[i-1][j])%MOD;
            f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*max(s-j+1,0)%MOD);
        }
        f[i][0]=f[i-1][0];
    }
     
    int ans=0,q=(n+k)>>1;
    for (re int i=q,d=1;i<=n;++i,d=MOD-d) //容斥计算答案
        ans=(ans+1ll*f[n][i]*d%MOD*C(i,q)%MOD*fact[n-i]%MOD)%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 53 PM

发表评论