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

danihao123 posted @ 2018年3月28日 21:51 in 题解 with tags 容斥原理 bzoj 广义容斥原理 , 1067 阅读
转载请注明出处:http://danihao123.is-programmer.com/

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

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;
}
NCERT Mathematics Sa 说:
Sep 28, 2022 01:16:24 PM

Mathematics is one of the subjects which plays a key role in everyone’s life and it’s very important to each student. NCERT Mathematics Sample Paper Class 2 Mathematics is not a certain time helping subject, it is along with the people for their whole life at any time and at anywhere. It should begin from the foundation of Education to enable 2nd students to understand mathematics easily. Downloading NCERT Mathematics Sample Paper 2023 Class 2 for all formats of exams conducted under Term-1, Term-2 and other types of exams has available for every candidate who wants to get a keen clarity on the question pattern of the exam paper along with revised important questions.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter