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

嘟嘟嘟

题中给的\(k\)有点别扭，我们转换成\(a > b\)的对数是多少，这个用二元一次方程解出来是\(\frac{n + k}{2}\)。

然后考虑dp，令\(dp[i][j]\)表示前\(i\)个数中，有\(j\)对满足\(a > b\)的方案数，转移的时候考虑这一组是否满足\(a > b\)即可：\(dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (num[i] - (j - 1))\)。其中\(num[i]\)表示比\(a[i]\)小的\(b[i]\)的个数。

求完这个还没有完事，因为我们只保证了有\(j\)个满足\(a > b\)，而剩下的位置并不清楚。

于是令\(g[i] = dp[n][i] * (n - i)!\)，表示\(n\)组匹配中，至少有\(i\)组满足\(a > b\)的方案数，因为剩下的\(n - i\)个位置是瞎排的，所以不知道是否会出现\(a > b\)。

令\(f[i]\)表示恰好有\(i\)个匹配满足\(a > b\)，那么能列出\(g[k] = \sum _ {i = k} ^ {n} C_{i} ^ {k} f[i]\)（其实自己并不是十分懂这一步），然后通过二项式反演就可以求出\(f[k] = \sum _ {i = k} ^ {n} (-1) ^ {i - k} C_{i} ^ {k} g[i]\)。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

#include<assert.h>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 2e3 + 5;

const ll mod = 1e9 + 9;

In ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

In void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

In void MYFILE()

{

#ifndef mrclr

  freopen("ha.in", "r", stdin);

  freopen("ha.out", "w", stdout);

#endif

}

int n, K, a[maxn], b[maxn], num[maxn];

In ll inc(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}

ll fac[maxn], C[maxn][maxn];

In void init()

{

  fac[0] = 1;

  for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;

  C[0][0] = 1;

  for(int i = 1; i <= n; ++i)

    {

      C[i][0] = 1;

      for(int j = 1; j <= i; ++j) C[i][j] = inc(C[i - 1][j - 1], C[i - 1][j]);

    }

}

ll dp[maxn][maxn];

int main()

{

  MYFILE();

  n = read(), K = (n + read()) >> 1;

  init();

  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);

  for(int i = 1; i <= n; ++i) num[i] = lower_bound(b + 1, b + n + 1, a[i]) - b - 1;

  dp[0][0] = 1;

  for(int i = 1; i <= n; ++i)

    {

      dp[i][0] = dp[i - 1][0];

      for(int j = 1; j <= i; ++j)

	dp[i][j] = inc(dp[i - 1][j] % mod, dp[i - 1][j - 1] * (num[i] - j + 1) % mod);

    }

  ll ans = 0;

  for(int i = K; i <= n; ++i)

    {

      int flg = (i - K) & 1;

      ll tp = C[i][K] * fac[n - i] % mod * dp[n][i] % mod;

      ans = inc(ans, flg ? mod - tp : tp);

    }

  write(ans), enter;

  return 0;

}

巴特西

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

最新文章

热门文章