danihao123's Blog

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

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

OI给了我足够的欢乐了，OI让我看到了新的世界，让我有了人生中最好的几位朋友，我没有什么可以遗憾的了……就算可能要面临最残酷的结局吧……

有点跑题了呢……还是说这个题吧

显然可以看出来这个题要求你的从大到小的匹配（姑且称之为好的匹配）恰好要有 $\frac{n + k}{2}$ 个，剩下的全都不是好的匹配。

首先把糖果（记为 $A$ ）和药片（记为 $B$ ）分别排序，对于每一个 $A$ 中元素就很容易得到 $B$ 中有多少比它小的。考虑设计状态 $f[i][j]$ 表示对（排序后的） $A$ 的前 $i$ 项，已经确定了的好的匹配有至少 $j$ 个。这个DP转移显然。

然后发现 $f[n][j]\times (n - j)!$ 就是对于所有元素的完美匹配中，有至少 $j$ 个是好的匹配的方案数。这正是广义容斥原理的用武之地。考虑记 $t_j = f[n][j]\times (n - j)!$ ，那么答案就是（令 $\frac{n + k}{2} = l$ ）：

$\sum_{i = l}^n (-1)^{n - i}\binom{i}{l} t_i$

代码：

/**************************************************************
    Problem: 3622
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1844 ms
    Memory:63680 kb
****************************************************************/
  
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000000009LL;
const int maxn = 2005;
ll C[maxn][maxn], F[maxn];
inline void process() {
  int N = 2000;
  C[0][0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    C[i][0] = C[i][i] = 1LL;
    for(int j = 1; j < i; j ++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha;
    }
  }
  F[0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    F[i] = (F[i - 1] * (ll(i))) % ha;
  }
}
  
int A[maxn], B[maxn];
ll cp[maxn]; int n;
void gen_cp() {
  std::sort(A + 1, A + 1 + n); std::sort(B + 1, B + 1 + n);
  for(int i = 1; i <= n; i ++) {
    cp[i] = n - (B + n + 1 - std::upper_bound(B + 1, B + 1 + n, A[i]));
#ifdef LOCAL
    printf("cp[%d] : %lld\n", i, cp[i]);
#endif
  }
}
  
ll f[maxn][maxn];
ll dp(int dec) {
  process(); gen_cp();
  f[0][0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j <= n; j ++) {
      f[i][j] = f[i - 1][j];
      if(j > 0) {
        f[i][j] += (f[i - 1][j - 1] * std::max(0LL, cp[i] - ll(j - 1))) % ha;
        if(f[i][j] >= ha) f[i][j] -= ha;
      }
#ifdef LOCAL
      printf("f[%d][%d] : %lld\n", i, j, f[i][j]);
#endif
    }
  }
  for(int j = 0; j <= n; j ++) {
    f[n][j] = (f[n][j] * F[n - j]) % ha;
  }
  ll ans = 0;
  for(int j = dec; j <= n; j ++) {
    ll a = ((j - dec) % 2 == 0) ? 1LL : (ha - 1LL);
    ll delta = (C[j][dec] * f[n][j]) % ha;
    ans += (a * delta) % ha;
    if(ans >= ha) ans -= ha;
  }
  return ans;
}
  
int main() {
  int k; scanf("%d%d", &n, &k);
  if((n - k) & 1) {
    puts("0"); return 0;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
  }
  printf("%lld\n", dp((n + k) / 2));
  return 0;
}

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

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器