Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

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

Posted on

dp，二项式反演

自己还是太弱了。

Solution

首先排序，再将k变成$\frac{n+k}{2}$，然后考虑dp，对于首先预处理出每个$a_i$最多可以和多少个$b_i$匹配产生贡献，考虑一下两种情况：

  • $a_i$和$b_i$匹配上，下一个$a_i$能匹配上的数的个数减一
  • 没匹配上，情况过于复杂，之后再讨论。

我们重新定义一个数组$f_i=(n-i)!dp_{n,i}$，代表至少有$i$个匹配上的情况，之后用二项式反演就可以得出答案。

二项式反演的式子为：$ans =\sum_{i=k}^n(-1)^{i-k}C_i^kf_i$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0'); 
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c){ putchar(c); }
template <>
inline void write(const char *s) { while(*s) putchar(*s ++); }
template<class T, class ...ARC>
inline void write(T res, ARC ...com){ write(res), write(com...);}
const int N = 2005, mod = 1e9 + 9;
int n, k;
int a[N], b[N];
int f[N][N], res[N];
int num[N], fac[N], inv[N], ans;
inline int C(int x, int y)
{
	if(x < 0 || x < y) return 0;
	return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod; 
}
inline void init()
{
	fac[0] = 1;
	for(int i = 1;i < N;i ++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[0] = inv[1] = 1;
	for(int i = 2;i < N;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	for(int i = 2;i < N;i ++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
int main()
{
	init();
	read(n, k);
	if(n + k & 1) return puts("0"), 0;
	k = n + k >> 1;
	for(int i = 1;i <= n;i ++) read(a[i]);
	for(int i = 1;i <= n;i ++) read(b[i]);
	sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
	for(int i = 1, l = 1;i <= n;i ++)
	{
		while(a[i] > b[l] && l <= n) l ++;
		num[i] = l - 1;
	}
	for(int i = 0;i <= n;i ++) f[i][0] = 1;
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= i;j ++)
			if(num[i] >= j - 1) f[i][j] = (f[i - 1][j] + 1ll * (num[i] - j + 1) * f[i - 1][j - 1] % mod) % mod;
			else f[i][j] = f[i - 1][j];
	for(int i = 1;i <= n;i ++) res[i] = 1ll * fac[n - i] * f[n][i] % mod;
	for(int i = k;i <= n;i ++) 
		if(i - k & 1) ans = (ans - 1ll * C(i, k) * res[i] % mod + mod) % mod;
		else ans = (ans + 1ll * C(i, k) * res[i] % mod) % mod;
	write((ans + mod) % mod);
	return 0;
}