bzoj 3622 已经没有什么好害怕的了
Description
Input
Output
Sample Input
4 2
5 35 15 45
40 20 10 30
Sample Output
4
HINT
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果,第三行是药片
题解
首先算一下应该有多少对$A_x > B_x$,发现$2x + k = n$,也就是$x = {n – k \over 2}$,那么$x + k = {n + k \over 2}$,那么$n + k \over 2$肯定要是个整数,所以可以先判下无解的情况。
现在的限制是很强的,要求恰好有k组,也就是说剩下的一定要是小于的情况。做这种容斥题就可以先考虑弱化它的限制,然后用容斥再满足它的限制。比如这种恰好k的就可以先dp出至少k的再容斥出来恰好的情况。
考虑一下至少k的怎么dp。$f[i][j]$表示A和B分别排序后,dp到了A组的第i个数字,A比B大的有j组。
这样的话因为两个数组都是有序的所以可以很方便地定位一段A比B大的前缀,设这段前缀一共有p个数,里面一开始已经选了j个,还剩下p-j个没有选,所以递推f[i+1]的时候就是:
$f[i][j] += f[i – 1][j]$(不限制第i个要大)
$f[i][j] += f[i – 1][j – 1] \times (p – j)$(限制第i个要大)
接下来就是容斥一下,设$g[i][j]$为有恰好j个小。我们发现对于一个$ f[i][j]$它的非确定A大于B的那些数对中,有$ (i−j)!$种排列。那么按照这种容斥
$$g[i][j]=f[i][j]\times (i−j)! − \sum_{k = j + 1}^n g[i][k] \times C^i_j$$
只要对于$i = n$的时候容斥一下就行了,g也不用求。
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 |
#include <cstdio> #include <algorithm> using namespace std; const int mod = 1000000009; int n, k, ans, a[2010], b[2010], C[2010][2010], mul[2010], f[2010][2010]; main() { scanf("%d%d", &n, &k); if ((n + k) & 1) return 0, puts("0"); k = (n + k) / 2; f[0][0] = 1; C[0][0] = C[1][0] = 1; for (int i = 1; i <= 2000; ++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; mul[0]=1; for (int i = 1; i <= n; ++i) mul[i] = 1ll * mul[i - 1] * i % mod; for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n); for (int i = 0, p = 0; i <= n; ++i) { while (b[p + 1] < a[i + 1] && p < n) ++p; for (int j = 0; j <= i; ++j) if (f[i][j] != 0) { f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod; if (p - j >= 0) f[i + 1][j + 1] = (f[i + 1][j + 1] + 1ll * f[i][j] * (p - j) % mod) % mod; } } for (int i = 0; i <= n; ++i) f[n][i] = 1ll * f[n][i] * mul[n - i] % mod; for (int i = k, dlt = 1; i <= n; ++i, dlt = -dlt) ans = (ans + 1ll * dlt * C[i][k] * f[n][i] % mod) % mod; ans = (ans + mod) % mod; printf("%d\n",ans); } |