bzoj3622: 已经没有什么好害怕的了

/*
首先解方程得到具体有多少个是大于的情况 
然后dp求出f[i]是至少有i个大于的情况
最后容斥一下就好了
 




*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll long long 
#define M 2020
#define mmp make_pair
using namespace std;
int read()
{
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
const int mod = 1000000009;

void add(int &x, int y)
{
    x += y;
    x -= x >= mod ? mod : 0;
    x += x < 0 ? mod : 0;
}

int mul(int x, int y)
{
    return 1ll * x * y % mod;
}


int f[M][M], a[M], b[M], c[M][M], fac[M], n, k; 
int main()
{
    n = read(), k = read();
    if((n - k) & 1) return 0 * puts("0");
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++) b[i] = read();
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    c[0][0] = 1, fac[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        fac[i] = mul(fac[i - 1], i);
        c[i][0] = 1;
        for(int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int tmp;
        for(tmp = 1; tmp <= n && b[tmp] < a[i]; tmp++);
        tmp--;
        for(int j = 1; j <= i; j++) f[i][j] = f[i - 1][j], add(f[i][j], mul(f[i - 1][j - 1], max(tmp - j + 1, 0)));
        f[i][0] = f[i - 1][0];
    }   
    int ans = 0;
    k = (n + k) >> 1;
    for(int i = k; i <= n; i++)
    {
        ll tmp = mul(f[n][i], mul(fac[n - i], c[i][k]));
        if((i - k) & 1) add(ans, -tmp);
        else add(ans, tmp);
    }
    cout << ans << "\n";
    return 0;
}

bzoj3622: 已经没有什么好害怕的了

原文：https://www.cnblogs.com/luoyibujue/p/10680340.html